Development of a novel evolutionary algorithm specialized for crystal structure prediction of molecular systems: MCaSP-Evo

Abstract

Katı bir kristal malzemenin kristal yapısı malzemeyle ilgili özelliklerin çoğunu belirler; bu özelliklere örnek olarak yoğunluk, mekanik özellikler, elektrik ve elektronik kabiliyetleri verilebilir ancak bununla sınırlı değildir. Bu nedenle bilinen malzemelerin hesapsal incelenmesi ve yeni malzemelerin bilgisayımsal keşfi önemli ölçüde kristal yapı hakkındaki bilgiye bağımlıdır. Kristal yapı hakkında güçlü mikroskoplarla elde edilen görüntüler gibi gözlemsel bilgiler bu konuda esastır; ancak yeni malzeme adayları ve gözlem kabiliyetlerimizin ötesindeki oluşumlar gibi ilgilenilen çok sayıda madde için ya tamamen ulaşılamaz durumdadır ya da güvenilir değildir. Dolayısıyla da kristal yapı tahmini, hesapsal malzeme tasarımı veya katı hal fiziği, malzeme bilimi ve hatta biyomoleküler aktivitelerin araştırmaları için olmazsa olmaz bir araç konumundadır. Başarılı bilgisayımsal tahmin yöntemlerinin eksikliği de ilgili araştırma ve geliştirme faaliyetlerinin önündeki başlıca engellerden biri olmuştur.Malzeme bilimindeki merkezi rolüne ve büyük önemine rağmen tahminlere yön veren başarılı ve genel olarak uygulanabilir bir teori ortaya çıkamamıştır, ve bilgisayımsal kristal yapı tahmininin (KYT) mümkün olup olmadığı bile yakın zamanlara dek tartışmalı olmuştur. Bilgisayımsal KYT yöntemlerinde bu binyılın ilk onyılındaki hızlı gelişmeye kadar kristal yapının geniş ölçüde öngörülemez olduğu düşünülürdü, ve görevin hesaplama karmaşıklığı ile kullanılan hesaplamalı kimya yöntemlerinin tatmin edici olmayan başarımları dolayısıyla ilgili çabalara şüphe ile yaklaşılırdı. Bu sınırlamalar büyük ölçüde aşıldı ve KYT çalışmaları önemli hedeflere ulaştı. Öte yandan bu alanın gelişimi hala devam etmektedir ve KYT uygulamaları henüz yakın gelecekte ulaşmaları beklenen işlevselliğe ulaşabilmiş değildir.KYT'nin genel tanımı, verili koşullar altında kararlı olan kristal yapıların tahmini olarak verilebilir; ancak daha az kararlı yapıların ve yarıkararlı yapıların bulunması da öenmli faydalar sağlamaktadır.KYT'nin genel prosedürü hedef molekül(ler) ve iyon(lar)ın tetkikini, aday çözümlerin üretilmesini ve değerlendirilmesini ve seçilen yapılan ayrıntılı incelenmesini içerir. Aday çözümlerin incelenmesi için en gözde yaklaşım serbest enerjilerinin hesaplanmasıdır, zira bu kristal yapının kararlılığı için en önemli özelliklerden birisidir; aday çözümlerin üretilmesi için en yaygın yaklaşım ise küresel eniyileme yöntemlerinde uygulanmış olan sezgisel ve üstsezgisel rutinler veya rastgele arama ile Sobol dizileri (Sobol tarafından geliştirilmiş olan ve arama uzayının farklı bölümlerini aynı veya yakın sıklıkla örneklemeyi hedefleyen bir sayı dizisi üretim yöntemi) gibi kaplam yöntemleri olarak verilebilir.Bu alandaki çoğu zorluk esnek moleküllerin, büyük moleküllerin, farklı moleküllerin ve iyonların kombinasyonlarını içeren veya büyük sistemlerin incelenmesi gibi özel uygulamalarda ortaya çıkmaktadır. Bu zorluklar aynı zamanda incelenen sistemlerde var olan parçacıkların tiplerine göre, yani moleküler ve atomik sistemler veya organik ve inorganik hedefler arasında değişkenlik göstermektedir, dolayısıyla özelleşmiş KYT yöntemleri arasındaki farklılaşma dikkate değerdir. Bu çalışmanın birinci bölümünün ilk kısmında KYT probleminin tarihinden ana hatlarıyla bahsedildi, bunu KYT'nin tanımı ve başlıca zorluklarıyla ilgili temel bilgileri sağlayan ikinci kısım takip etmektedir. KYT için en önemli yöntem toplam enerjinin minimizasyonu olarak kalmaktadır, ancak çekirdeklenme hızı veya moleküler dinamik analizi gibi başka özellikler de benzer serbest enerji düzeylerindeki kristal yapıların arasından seçim yapmak için işlevsel olabilmektedir. Enerji hesabının isabetliliği ve güvenilirliği eniylemenin performansı açısından can alıcı öneme sahiptir, ancak en başarılı enerji hesaplama yöntemlerinin yüksek maliyetleri bir ödünleşim durumu yaratmaktadır ve enerji hesaplama yönteminin seçimini probleme ve eldeki kaynaklara bağımlı hale getirmektedir.Serbest enerji hesaplama yöntemlerinin sınıflandırılması şu şekildedir: ab inito yöntemler, ki bunlar hesapsal maliyetleri en yüksek ve en güvenilir olan hiçbir deneysel veri kullanmayan yöntemlerdir; DFT yöntemleri ki bunlar da ab initio yöntemlerin daha düşük maliyetli bir çeşididir; ab initio yöntemlere yarıdeneyimsel yaklaşımlar; ve son olarak en uygun maliyetlileri olup doğru şekilde üretildiğinde ve kullanıldığında yeterli isabetliliği elde etmeye imkan veren kuvvet alanları gibi deneyimsel yaklaşımlar. Bu yöntemler birinci bölümün ikinci kısmında özetlenmiş ve açıklanmıştır.İkinci bölüm küresel eniyilemeye açıklayıcı bir girişe ve küresel eniyileme yöntemlerinin başlıca sınıflarının doğa esinli yöntemlere önemli KYT uygulamalarını da içeren özel bir yer vererek incelenmesine ayrılmıştır. Grubumuzda geliştirilmiş olup bu çalışmadan farklı amaç fonksiyonları veya eniyileme yöntemleri kullanan başka algoritmaların incelenmesi bunlardan sonraki kısımda gelmektedir, bunu da yapay zeka ve daha başka uygulamalara değinilen son kısım takip etmektedir. Evrimsel Algoritmalar (EAlar) için üçüncü bölüm ayırıldığından dolayı burada bahsedilmemiştir.EAların tarihsel arkaplanı ve genel yapısı üçüncü bölümde verilmiştir. Bizim uygulamamıza da yön vermiş olan temel kavramlar ve değerlendirmeler bizim çalışmamız için en önemli olan yönleri vurgulanmak kaydıyla özetlenilmiştir. Bunu takiben ileri çalışmalarımızda uygulanma potansiyeli olan gözde ve gelecek vaadeden EA türlerine kısaca değinilmiştir. Son kısımda bahsedilmek üzere ise KYT alanında en ciddi başarıları elde eden iki EA, USPEX ve GAtor seçilmiştir.Son bölümde bizim uygulamamızın sunuşu algoritmik parçaları ve alana özgü operatörleri gerekli açıklamalar ve ilgili içeriğin seçilmesinde belirleyici olan etmenlerden bahsedilmesi yoluyla gerçekleştirilmiştir. Çalışmamızı gelecekte sırtlama potansiyelinden ötürü, altyapı keşfi anlayışı özellikle vurgulanmış ve altında yatan motivasyonlar açıklanmıştır.Bunları özet olarak belirtmek gerekirse, öncelikle yöntemin gelişim çizgisi göz önünde bulundurularak bu aşamada yerel eniyileme yöntemlerinin her aday çözüm için kullanılması yoluna gidilmemiş ve bu katkı sonraya bırakıldı. Olgunlaşmamış yakınsama problemini ortadan kaldırmak için sırasıyla mutasyon sıklığı gibi süperparametrelerin eşzamanlı kontrolü, popülasyon yakınsama kriterini sağladığında rastgele bireylerle yeniden başlatılmasını ve en iyi iki bireyin 150 nesil sonra yeniden dahil edilmesini içeren bir yeniden başlatma önlemi, yükleme (crowding) katılma (reinsertion) tasarımı, ve ada modeli paralelleştirmesi yöntemleri uygulandı. Alana özgü operatör olarak ise ilk olarak moleküllerin pozunu, yani pozisyonunu ve yönelimini belirleyen parametrelerin dağıtılmadan değiştirilmesini sağlayan bir çaprazlama (crossover) yöntemi kullanılmış, bunu en kötü moleküller arası etkileşimin iki tarafından toplamda yapının enerjisine daha kötü bir katkı sağlayan molekülün diğer tarafındaki moleküle göre pozunu değiştiren bir mutasyon operatörü takip etmiştir. Son olarak ise moleküller arasındaki iyi yani düşük enerjili etkileşimleri bozmadan çaprazlama yapmak için bu etkileşimlerin her iki tarafındaki molekülü de aynı ebeveynden ve aralarındaki göreli pozu koruyarak alan bir çaprazlama operatörü geliştirilmiştir. Bunun yaratabileceği bir yapısal meyili engellemek için özellikle iyi etkileşimler sağlayan bağları hedef alan bir mutasyon operatörü de ilave edilmiş, bunun altyapı açısından popülasyon yakınsadığında mutasyon ihtimalinin artırılması yoluyla dinamik kontrolü de sağlanmıştır.Bunlara ek olarak, yükleme (crowding) ve göç (migration) işlemlerinde birey seçimi için kullanılan bireyler arası uzaklık hesabı da alana özgü tecrübeleri ve bilgileri hesaba katarak oluşturulmuştur ve moleküller arası mesafeleri KYT açısından anlamlı olacak bir sıra değiştirme sonrasında hesaplamakla birlikte kafes parametreleri ile moleküler parametrelerin etkisini anlamlı bir şekilde dengelemeyi hedeflemektedir.Sonuç olarak, önemini ve farklı biçimleri incelenen sitozin molekülünün iki moleküllü kristal yapısının doğru olarak tahmin edilebildiği düzeye ulaşılmıştır.

Crystal structure of a solid material determines most of the properties of a material, including but not limited to density, mechanical properties, electrical and electronic abilities. Therefore, computational discovery of novel materials and computational examination of known materials is significantly dependent on the information about crystal structure. Observational information of crystal structure, such as transmission electron microscopy images or other high-powered microscopy outcomes, is essential for this purpose; but it is not reliable or totally absent for many substances of interest, such as new material candidates or formations beyond our observation abilities. Hence, prediction of crystal structure serves as an indispensable tool for many research areas as computational materials design or research activities to gain insight about solid state physics, materials, or even biomolecular activities. The lack of successful computational prediction tools were/are one of main obstacles for scientific development of related research and development efforts.Despite its central role and primary importance in material science, a successful and generally applicable theory leading predictions is absent; and computational crystal structure prediction (CSP) was arguable for even being possible. Until the fast development of computational methods for CSP in the first decade of our millennium, it was extensively considered that crystal structures are unforeseeable and related attempts were doubted due to computational complexity of the task and unsatisfactory performances of used computational chemistry tools. These limitations are mostly overcome, and CSP studies achieved important goals. On the other hand, the development of the field is still ongoing, and CSP applications are not yet as functional as they are expected to be in the close future.The general definition of CSP can be given as the prediction of stable crystal structure at given conditions, whereas finding less stable or metastable structures may also be an important interest.The general procedure of CSP includes investigation of target molecule(s) and ions, production and tests of candidate solutions and detailed examination of selected structures. The most popular approach for evaluation of candidate solutions is calculation of free energy, as it is one of the most important characteristics for stability of crystal structure; and the most common approach for production of candidate solutions is heuristic or metaheuristic routines implemented in the global optimization of free energy, or coverage methods such as random search or Sobol sequences.Most challenges in the field emerge in special applications such as investigation of flexible molecules, large molecules, combinations of different molecules and ions, or large systems. Also, those differ according to the particle type present in the examined systems, i.e. between molecular and atomic system or organic and inorganic targets, so that the distinction among specialized CSP methods is noteworthy. First part of the first chapter outlines history of CSP problem in the first section, which is followed by the second section that provides essential information about the definition and major challenges of CSP.The major method for CSP remains minimization of free energy, whereas some other properties such as nucleation rate or molecular dynamics analysis may also be useful for selecting among crystal structures with similar free energies. The accuracy and reliability of energy calculation is crucial for the optimization performance, on the other hand, high costs of most successful energy calculations create a trade-off condition and make the selection of energy method dependent on the problem and resources at hand.Total energy calculation methods are classified as ab initio methods, which are the most computationally expensive and reliable ones. DFT is a special case of ab initio methods with lower cost. Semi-empirical approximations cheaper than DFT are also available. The fastest and most affordavle approach to calculate the energy is the empirical methods such as force fields, that may exhibit sufficient accuracy when generated and used properly. These methods are summarized and explained in the second part of the first chapter.The second chapter is dedicated to an explanatory introduction to the global optimization, by examining of its major classes with a special emphasis on nature-inspired methods, including their principal implementations for CSP problem. Other CSP procedures with different objective functions and optimization methods developed by our group are explained in the following part, followed by mentions on various artificial intelligence algorithms and other applications. Evolutionary Algorithms (EAs) are not included as the third chapter is dedicated to those. Historical background and general structure of EAs is provided in the third chapter. Basic concepts and considerations in EA design, which guided our implementation process, are summarized and most important factors for our study are highlighted, followed by very brief mention on potential future additions to our implementation in the section of examples for popular and promising variations of EA. Among many other examples, two most promising EAs on CSP are chosen to mention in the last part, namely USPEX and GAtor.In the last chapter, our implementation is presented by its algorithmic components and domain-specific operators, together with explanations and decisive considerations in the selection of related content. The concept of substructure discovery is especially emphasized and underlying motivations are explained, for its potential to carry our work in the future.