Heuristic algorithms for solving chemical shift assignment problem in protein structure determination

Abstract

Heuristic algorithms have been widely used in several different hard optimization problems not only in computer science but also in several other disciplines, including natural sciences, bioinformatics, electronics, and operational research, where computational methods are needed. Heuristic algorithms search for optimal solutions by maximizing or minimizing the given objectives depending on the need while satisfying the given conditions. Heuristic algorithms find solutions in a huge search space where many different possible solution candidates exist. Due to these conditions of the search space, systematic search techniques are not feasible for such kinds of problems. In this thesis, we applied several different heuristic approaches and their combinations on the chemical shift assignment problem of the Nuclear Magnetic Resonance (NMR) spectroscopy. NMR spectroscopy is one of the methods to determine the three-dimensional structure of proteins. The three-dimensional structure of proteins provides crucial information to detect the shape, structure and function of biological macromolecules. The protein structure also demonstrates the function of proteins by illustrating the interactions of the macromolecules with other proteins or small ligands. Therefore, the three-dimensional structure of a protein can form a basis for drug design against human diseases. NMR has many advantages compared to other techniques; however, NMR spectroscopy needs very advanced computational techniques for providing the protein structure. The chemical shift assignment of the atoms is one of the most challenging problems in NMR spectroscopy. It needs a considerable amount of time by an experienced spectroscopist if the determination is done manually or by a semi-automated method. Additionally, even if the remaining parts of the structure determination methods work perfectly, it is impossible to create the protein structure if the chemical shift assignments are not done correctly. Due to this complexity, the total number of protein structures obtained from NMR spectroscopy is very few compared to its alternative methods, such as X-ray crystallography. Due to its importance in NMR experiments, the chemical shift assignment problem has recently become one of the most critical research areas in the computational techniques of NMR spectroscopy. There have been many types of research on this problem; however, they are far from perfect. Some of these techniques can provide only partial solutions by assigning only the backbone atoms or only the sidechain atoms. Some of these methods require a very long computation time. Additionally, the results of many of the existing methods have a great area for improvement. In this thesis, we developed a novel method with the heuristic algorithms that provides a fully automatic assignment of the chemical shift values of NMR experiments. First, we studied the background of the problem along with the existing methods. Secondly, we proposed our methods that solve the problem with evolutionary algorithms. Thirdly, we performed experiments on several different datasets, compared the success of our methods against the state-of-the-art solutions of the problem, and continuously improved our methods. Finally, we performed further analysis on the results and proposed further work. First, the background of the chemical shift assignment problem is comprehensively studied from the computer science point of view. The optimization processes in heuristic algorithms, stochastic local search methods, iterative improvement, simple stochastic local search methods, hybrid, and population-based stochastic local search methods are discussed in detail. The ant colony optimization and the evolutionary algorithms are analyzed as the population-based stochastic local search methods. After these evaluations, the evolutionary algorithms appeared to be a suitable candidate for solving this problem since they already work with a population, which is a set of solution candidates. We also analyzed the NMR spectroscopy hardware, principles, and experiment steps in detail because the problem is a real application from NMR spectroscopy in natural sciences. Furthermore, we had a deep dive into the chemical shift assignment problem and into the protein structure and peptide formation areas, which are the basis for the NMR spectroscopy calculations. Afterwards, the existing methods for solving this problem are discussed with their drawbacks. Secondly, we proposed our methods for solving the problem with heuristic algorithms. Our method comprises several different evolutionary algorithms and their combinations with hill climbing, with each other, and constructive heuristic methods. More conventional approach genetic algorithm, GA, and multi-objective evolutionary algorithms, NSGA2 and NSGA3, are applied to the problem. The multi-objective evolutionary algorithms investigated each objective parameter separately, whereas the genetic algorithm followed a conventional way, where all objectives are combined in one score function. While defining the methods, we first defined the problem model, along with the existing conditions and the score function. We modeled the problem as a combinatorial optimization problem, where expected peaks are mapped onto the measured peaks. The chromosome of the algorithm is an array of the expected peaks and the values inside represent their mapped measured peaks. The objectives of the problem are defined in a score function. The constraints are not separately evaluated because they are already fulfilled by the problem model implicitly. Additional fine-tuning and changes are implemented on the algorithms to apply the NMR-specific behaviors to the problem model. Then, the following improvements are realized on the algorithms: We optimized the probability of applying crossover and mutation in the methods. The population initialization is optimized with a constructive initialization algorithm, which minimizes the search space to find better initial individuals. Furthermore, we optimized the population's diversity to find the optimum solutions by escaping from local optima. We also implemented hybrid algorithms by combining a hill-climbing algorithm with our proposed algorithms. Thirdly, we performed experiments on several datasets with a set of commonly used spectra. We also compared the results of our methods with the two state-of-the-art algorithms: FLYA and PINE. In almost all of these datasets, our algorithm GA yielded better results than PINE. Our algorithm NSGA2 produced better results than PINE in almost half of the datasets. Our NSGA3 algorithm yielded less than 10% correct assignments because only two objectives out of four objectives of our problem model create trade-off. NSGA3 algorithms are known to be successful on problems with more than three objectives. Additionally, our algorithms had better runtime performance than FLYA in more than half of the datasets. Our algorithms could assign all of the atoms in all datasets, which creates a huge completeness success of the problem, whereas FLYA and PINE algorithms could not provide a complete assignment. Furthermore, we observed in our results that splitting a large protein into smaller fragments improved our algorithms' results dramatically. Finally, we performed further analysis on our results. These analyses showed us that our algorithms often assigned different atoms than FLYA and PINE. Primarily the GA algorithm can provide good results on some parts of datasets where the state-of-the-art algorithms cannot make any assignment. In order to leverage this success of our algorithms, we proposed a hierarchical method. This method combines FLYA and our algorithm GA to benefit from the different success factors of each algorithm. The results showed that this approach improved the overall success of the algorithms. In future work, the three algorithms could be combined to achieve better results. Additionally, one can focus on distinguishing atoms that can be assigned consistently and more reliably than others. The assignment is only tentative so that fewer wrong assignments are done. Furthermore, the objective function of the problem can be remodeled to improve the performance of the algorithms. Additionally, our method can be extended in further work so that large proteins are split into smaller fragments before applying our algorithms, which will improve the overall results. In this thesis, we successfully implemented a fully automatic algorithm for solving the chemical shift assignment problem of NMR spectroscopy. Our method can automatically assign a significant part of the sidechain and backbone atoms without any parameter changes or manual interactions. We produced results that are comparable to the two very well know state-of-the-art algorithms. Our approaches could provide around a 70% success rate on these datasets and assign many atoms that other methods could not assign. Our algorithm outperformed at least one of these two state-of-the-art methods almost in all of our experiments. Additionally, the whole methods are implemented on the MOEA framework, enabling the further implementation of new algorithms easily.

Sezgisel algoritmalar zor eniyileme problemlerinin çözümü için sadece bilgisayar bilimlerinde değil; doğal bilimler, biyoenformatik, elektronik ve yöneylem araştırması gibi hesaplamalı yöntemlere ihtiyaç duyulan diğer bilim alanlarında da sıklıkla kullanılır. Sezgisel algoritmalar, verilen amaç fonksiyonlarını ihtiyaca göre enazaltarak ya da ençoklayarak ve verilen kısıtları karşılayarak eniyi çözümü ararlar. Sezgisel algoritmalar çok fazla farklı olası çözüm adayı bulunan çok büyük arama uzaylarında çözüm bulmak için kullanılırlar. Arama uzayındaki bu şartlar sebebiyle, bu tür problemlerde sistematik arama tekniklerini uygulamak olanaklı değildir. Biz bu tezde, birçok farklı sezgisel algoritma ve onların birbirleriyle birleşimini Nükleer Manyetik Rezonans (NMR) spektroskopisinde yer alan kimyasal kayma atama probleminin çözümünde uyguladık. NMR spektroskopisi proteinlerin üç boyutlu yapılarının tespiti için kullanılan yöntemlerden biridir. Proteinlerin üç boyutlu yapısı, biyolojik büyük moleküllerin şekli, yapısı ve görevlerinin tespiti için çok önemli bilgiler sağlar. Protein yapısı ayrıca büyük moleküllerin diğer proteinlerle ve küçük ligandlarla olan etkileşimlerini göstererek proteinlerin görevlerini anlamamızda yardımcı olur. Bu yüzden, proteinlerin üç boyutlu yapısı insan hastalıklarına karşı ilaç tasarımında temel oluşturur. NMR diğer yöntemlerle karşılaştırıldığında birçok avantaja sahiptir. Örneğin, NMR alternatifi bir yöntem olan X-ışınları örütbilimi ile proteinlerin üç boyutlu yapılarını belirlemek için, proteinlerin kristalleştirilmesi gerekir. Kristalleştirme hem uzun zaman alan hem de proteinlerin doğal ortamı olan sıvı ortamdan çıkmalarına sebep olan bir yöntemdir. NMR spektroskopisinde hem kristalleştirme gibi zaman alan bir işleme ihtiyaç olmaz hem de proteinlerin doğal ortamları olan sıvı ortamda üç boyutlu yapılarının tespiti sağlanır. Fakat NMR spektroskopisi protein yapısının oluşturulması için çok ileri hesaplama tekniklerine ihtiyaç duyar. NMR spektroskopisi protein yapılarını doğrudan üretmez, onun yerine NMR spektrumu olarak bilinen sinyaller üretir. İleri hesaplama teknikleri kullanılarak, bu sinyaller üzerinden hesaplamalar yapılması ve üç boyutlu yapının bilgisayar yöntemleri ile oluşturulması gerekir. Yapılan hesaplama adımları içinde, en zor adım atomların kimyasal kayma frekanslarının atanması problemidir. Bu işlem, deneyimli bir spektroskopist tarafından elle ya da yarı otomatik bir metotla yapıldığında ciddi miktarda zamana ihtiyaç duyulur. Zor bir problem olmasının yanı sıra, kimyasal kayma problemi proteinlerin üç boyutlu yapısının doğru bulunmasında çok önemli bir yere sahiptir. Protein yapı belirleme metotları mükemmel olsa da, kimyasal kayma atamaları doğru yapılmadığında, protein yapısını belirlemek imkânsızdır. Bu yöntemin bu kadar zor olması sebebiyle, NMR spektroskopisinden elde edilen protein yapı sayısı, X-ışınları örütbilimi gibi diğer alternatif metotlarından üretilenlere göre çok düşüktür. NMR deneylerindeki öneminden dolayı, kimyasal kayma atama problemi son zamanlarda NMR spektroskopisi hesaplamalı teknikleri konusundaki en önemli araştırma alanlarından biri olmuştur. Bu problem üzerinde yapılmış birçok araştırma vardır, ancak bu yöntemler mükemmelden uzaktır. Bu yöntemlerden bazıları sadece yan zincir atomlarını ya da sadece omurga atomlarını atayarak sadece parçalı çözüm sunabilmişlerdir. Bu yöntemlerden bazıları da çok uzun hesaplama zamanlarına ihtiyaç duyarlar. Ek olarak, var olan yöntemlerin çoğunda sonuçların iyileştirilmesi gerekir. Bu tezde, sezgisel algoritmaları kullanarak NMR deneylerinde tam otomatik kimyasal kayma ataması yapan yeni bir metot geliştirdik. Tezin ilk aşamasında, problemin detaylarını ve bu konuda yapılan geçmiş araştırmaları inceledik. İkinci aşamada, evrimsel algoritmalar ile bu problemi çözecek metotlarımızı tasarladık. Üçüncü aşamada, farklı veri kümeleri üzerinde deneyler gerçekleştirerek, metotlarımızın sonuçlarını bu alandaki en gelişmiş algoritmalarla karşılaştırdık ve kendi metotlarımız üzerinde iyileştirmeler yaptık. Son olarak, elde ettiğimiz sonuçlar üzerinde detaylı analiz yaparak, ileride yapılacak çalışmalar için çeşitli öneriler oluşturduk. İlk aşamada, kimyasal kayma atama probleminin detaylarını ve bu konuda yapılan geçmiş araştırmaları bilgisayar bilimleri bakış açısı ile inceledik. Sezgisel algoritmalardaki eniyileme süreçleri, olasılıksal yerel arama yöntemleri, tekrarlayan iyileşme, basit olasılıksal yerel arama yöntemleri, melez ve toplum temelli olasılıksal yerel arama yöntemleri detaylı olarak incelendi. Toplum temelli olasılıksal yerel arama yöntemleri olan karınca kolonisi optimizasyonu ve evrimsel algoritmaları detaylarıyla değerlendirdik. Bu incelemeler sonrasında, evrimsel algoritmaların zaten çözüm adaylarını içeren bir toplumla çalıştıkları için, bu problemin çözümü için uygun bir aday olduğu kararına vardık. Algoritmalarımız ile çözeceğimiz problem doğal bilimlerden NMR spektroskopisinin gerçek bir uygulaması olduğu için, NMR spektroskopisinin donanımını, prensiplerini ve deney adımlarını da detaylı olarak inceledik. Ek olarak, kimyasal kayma problemi ile NMR spektroskopi hesaplarının temeli olan protein yapısı ve peptit oluşumunu da detaylı olarak analiz ettik. Bu analizler sayesinde problemin modellenmesi ve kullanılacak metotların iyileştirilmesi için gereken ön hazırlıkları tamamladık. Daha sonra, bu problemin çözümü için var olan metotları inceledik. Bu metotların her biri için, içerdikleri güçlü yanları ve hesaplamalarda karşılaştıkları zorlukları ele alarak, detaylı analiz yaptık. İkinci aşamada, bu problemin çözümü için sezgisel algoritmalar kullanarak kendi metotlarımızı oluşturduk. Bizim metodumuz birçok farklı evrimsel algoritma ile onların hem kendileriyle hem de tepe tırmanma algoritması ile yapıcı sezgisel yöntemlerle birleşmesinden oluşmaktadır. Yöntemleri belirlerken, öncelikli olarak problem modelini ve modeldeki kısıtları ve skor fonksiyonunu belirledik. Kısıtları ve amaçları içeren problem modelini her algoritma için aynı olarak belirledik ve yönteme göre problem modelimizde değişiklik uygulamadık. Biz problemi beklenen zirvelerin ölçülen zirvelere eşleştirildiği bir birleşimsel eniyileme problemi olarak modelledik. Bu problem modelini çözmek için, daha geleneksel bir yöntem olan genetik algoritma, GA, ile NSGA2, NSGA3 gibi çok amaçlı evrimsel algoritmaları probleme uyguladık. Genetik algoritma geleneksel bir yöntem izleyerek, tüm amaç parametrelerini tek bir skor fonksiyonunda birleştirerek çözüm bulmaya çalışır. Diğer taraftan, çok amaçlı evrimsel algoritmalar olan NSGA2 ve NSGA3 algoritmaları her amaç parametresini diğerlerinden bağımsız olarak ele alır. Problemin amaçlarını skor fonksiyonunda tanımladık. Problem modelinde kısıtları ayrıca hesaplamadık çünkü problemi tanımlama yöntemimizle tüm kısıtlar dolaylı olarak kapsanmış ve gerçekleştirilmiş oldu. Problemi çözmek için kullanacağımız evrimsel algoritmalarının kalıtım ipliğini, beklenen zirvelerin bir dizisi olarak belirledik. Bu dizinin içindeki değerler ilgili beklenen zirvenin atandığı ölçülen zirveyi gösterecek şekilde kalıtım ipliğini modelledik. Problem modelinde NMR'a özel davranışların uygulanması için, algoritmalarda çeşitli değişiklikler yaptık. Öncelikli olarak, problemin birden fazla spektrumda çalışabilmesi için, kalıtım ipliğinin her spektrum için genişletilmesini tasarlayarak modelimizi güncelledik. Atom sıralarının her spektrum için beklenen ve ölçülen zirvelerde farklı olduğunu ve bir zirvede aynı atomun birden fazla kez bulunabildiğini testlerimizde görerek, modelimizi güncelledik. NMR hesaplamaları sırasında birden fazla atomu temsil eden sahte atom olarak adlandırılan atomların referans değerlerinin hesaplanması algoritmasını da yaptığımız deneyler yardımıyla oluşturarak, yöntemimizi bu hesaplamayı kapsayacak şekilde geliştirdik. Modelimizi ve algoritmalarımızı tamamladıktan sonra, farklı veri kümeleri üzerinden testler yaparak, algoritmalarımızda çeşitli iyileştirmeler yaptık. Öncelikle, geçiş ve mutasyon olasılıklarını hem sabit, hem de arama uzayının büyüklüğü ile orantılı olarak değişen değerler vererek; bizim problemimiz için en uygun olan değerlerini belirledik. Problemin en büyük zorluklarından birisinin arama uzayının çok büyük olması olduğunu zaten önceden de belirlemiştik. Algoritmalarımızı başlatırken toplumun tüm bireylerini rastgele oluşturmak yerine daha iyi bireylerin oluşturulmasını sağlayan bir algoritma geliştirdik. Bu algoritma ile arama uzayını küçülterek, yapıcı ve sezgisel bir şekilde toplumun bireylerini oluşturduk. Ayrıca, yerel eniyiden kaçarak global eniyi çözümleri bulmak için toplumdaki çeşitlilik değerini belirledik. Toplumu oluşturan birey sayısını farklı veri kümeleri üzerinde denemeler yaparak, uygun bir değeri varsayılan değer olarak belirledik. Aynı şekilde, algoritmalarımızın içinde yer alan tekrarlama parametresi değerini de eniyileştirerek, varsayılan bir değer belirledik. Ek olarak, bizim evrimsel algoritmalarımızın her tekrarlamada buldukları bireyleri, arama uzayında bulundukları alanın en iyisi olarak iyileştirmek için, tepe tırmanma algoritması geliştirdik. Evrimsel algoritmalarımız ile tepe tırmanma algoritmasını birleştirerek oluşturduğumuz melez algoritmaları da problem üzerinde uyguladık. Tezin üçüncü aşamasında, deneylerimizi, yaygın bir şekilde kullanılan spektrum kümelerini içeren çeşitli veri kümeleri üzerinde gerçekleştirdik. Ayrıca sonuçlarımızı FLYA ve PINE gibi bu konudaki en gelişmiş algoritmaların sonuçları ile karşılaştırdık. Bizim GA algoritmamız, bu veri kümelerinin neredeyse tamamında PINE'dan daha iyi sonuçlar üretti. Bizim NSGA2 algoritmamız da bu veri kümelerinin neredeyse yarısında PINE'dan daha iyi sonuçlar üretti. Bizim NSGA3 algoritmamız bu veri kümelerinde %10'dan fazla doğru atom ataması yapamadı. Bunun sebebini incelemek için amaç fonksiyonlarının değerlerini her tekrar sonrasında inceledik ve problem modelimizdeki dört amaçtan sadece iki tanesinin birbiriyle çelişki oluşturduğunu belirledik. NSGA3 algoritmaları üçten fazla birbiriyle çelişen amacın bulunduğu problemlerde başarı elde ederler. Ek olarak, bizim algoritmalarımız veri kümelerinin yarıdan fazlasında FLYA'dan daha hızlı çalışma performansı gösterdiler. Bizim algoritmalarımız, veri kümesindeki tüm atomların atamasını yaparak çok yüksek tamamlık başarı oranına ulaştılar. Öte yandan, FLYA ve PINE algoritmaları tam bir atama yapamadılar. Ek olarak, yaptığımız deneylerde büyük proteinlerin küçük parçalara bölünmesi ile bizim metodumuzun yaptığı doğru atama sayısının %36 oranında arttığını ve yapılan yanlış atamanın da %36 oranında azaldığını gözledik. Tezin son aşamasında, sonuçlarımız üzerinden problem modeli ve atanan atomları içeren analizler yaptık. Yaptığımız analizlerde bizim algoritmalarımızın FLYA ve PINE'ın hiç atama yapamadığı birçok atomu başarıyla atayabildiğini gözledik. Özellikle GA algoritması veri kümesinde, en gelişmiş algoritmaların hiç atama yapamadıkları yerlerde iyi sonuçlar üretti. Bizim algoritmalarımızın bu başarısından faydalanmak için sıra düzenli yeni bir yöntem tasarladık. Bu yöntem ile FLYA ve bizim GA algoritmaları birbirinin başarılarından faydalanarak sonuca ulaştılar. Sıra düzenli yaklaşım ile elde ettiğimiz sonuçlar, tüm veri kümeleri üzerinde en gelişmiş algoritmaların sonuçlarını geçerek, genel başarı oranlarını yükseltmiştir. İlerleyen çalışmalarda, bizim bu tezde önerdiğimiz üç algoritma birleştirilerek daha iyi çözümler üretilebilir. Ayrıca, atomların tutarlı olarak ataması ve daha güvenilir atamasına odaklanarak, yanlış yapılan atama sayılarının düşürülmesi üzerinde çalışma yapılabilir. Ek olarak, problemin amaç fonksiyonu yeniden modellenerek performans iyileştirilebilir. Ayrıca, ilerleyen çalışmalarda bizim metodumuz, büyük proteinlerin küçük parçalara bölünmesi ve sonra algoritmaların uygulanması şeklinde genişletilirse, daha iyi sonuçlar elde edilebilir. Bu tezde, kimyasal kayma problemini çözen ve tamamen otomatik çalışan bir çözüm geliştirdik. Bizim yöntemimiz, herhangi bir parametre değişikliği ya da elle etkileşim olmadan hem yan zincir atomlarının hem de omurga atomlarının önemli bir kısmını başarıyla atayabilmektedir. Bizim sonuçlarımız bu konudaki en gelişmiş iki algoritmaların sonuçları ile karşılaştırılabilir seviyededir. Bizim yöntemimiz ile bu veri kümelerinde ortalama %70 oranında başarı elde edildi ve bizim yöntemimiz diğer yöntemlerin atama yapamadığı birçok atomun başarıyla atamasını yapabilmiştir. Bizim yöntemimiz, yaptığımız deneylerin hemen hemen hepsinde, bu alandaki en iyi algoritmaların en az birinden daha iyi sonuçlar elde etmiştir. Bizim yöntemimiz, çok amaçlı evrimsel algoritmalar kullanılarak modellendiği için, yeni bir amaç ya da kısıt eklenmesi ya da çıkarılması çok pratik bir şekilde problem modeli güncellenerek geliştirilebilir. Son olarak, bizim yöntemimiz MOEA çerçevesi üzerinde geliştirildiği için, bu çerçeve üzerinde geliştirilen yeni algoritmaların bu problemde uygulanması çok kolay bir şekilde yapılabilecektir.