Развој метода за анализу сличности биолошких секвенци на основу карактеристика поновака

Abstract

Анализа сличности биолошких секвенци омогућава утврђивање функционалних, структурних и еволуционих односа између различитих организама. Међутим, сличност биолошких секвенци и утвђивање особина нових нуклеотидних и протеинских секвенци су рачунарски захтевне методе у биоинформатици што намеће потребу за даљим развојем метода и алгоритама за њихово поређење. У складу са брзим растом и доступношћу велике количине биолошких података, нови алгоритми се развијају са циљем што ефикасније и прецизније обраде ових података. Један од изазова код одређивања сличности биолошких секвенци јесте издвајање скупа значајних атрибута секвенци, чија кардиналност може да буде велика за примену у постојећим методама за одређивање сличности елемената. Стога је од изузетног значаја имати једноставан и ефикасан алгоритам за одређивање међусобних односа биолошких секвенци. Циљ овог рада је формирање и имплементација нових метода за анализу сличности секвенци на основу статистички значајних поновака различитих дужина и типова. Прва метода се заснива на теорији информација узимајући у обзир позицију и учесталост статистички значајних поновака, за које се не очекује такво присуство у случајно генерисаној секвенци исте дужине. Друга метода садржи формирање потписа секвенци и профила таксономских категорија на основу парова понављајућих делова секвенци, као и растојања између елемената тих парова. Идеја ове методе је представити секвенце мањим бројем карактеристичних тачака у циљу препознавања истих као код алгоритама за препознавање лица. Предложене методе су тестиране на различитим референтним скуповима биолошких секвенци и резултати су упоређени са резултатима добро познатих и ефикасних алгоритама који се заснивају на поравнању (BLAST, Clustal Omega) и алгоритама без поравнања који се заснивају на к-торкама. Добијени резултати показују висок ниво конзистентности са резултатима метода са којима је извршено поређење. Прецизност предложених метода није била мања од вредности добијених за постојеће методе са којима су резултати упоређивани за већи број спроведених тестирања, док је брзина добијања резултата зависила од рачунарске инфраструктуре и примера секвенци. Предложене методе представљају значајну допуну постојећим методама за одређивање сличности биолошких секвенци, јер се досадашње методе за анализу сличности биолошких секвенци нису заснивале на статистички значајним поновцима различитих карактеристика

The analysis of biological sequence similarity between different species is significant in identifying functional, structural or evolutionary relationships among the species. Biological sequence similarity and analysis of newly discovered nucleotide and amino acid sequences are demanding tasks in bioinformatics. As biological data is growing exponentially, new and innovative algorithms are needed to be constantly developed to get faster and more effective data processing. The challenge in sequence similarity analysis algorithms is that sequence does not always have obvious features and the dimension of sequence features may be very high for applying regular feature selection methods on sequences. It is important to have a simple and effective algorithm for determining biological sequence relationships. This thesis proposes two new methods for sequence transformation in feature vectors that takes into consideration statistically significant repetitive parts of analyzed sequences, as well as includes different approaches for determination of nucleotide sequence similarity and sequence classification for predicting taxonomy groups of biological sequence data. The first method is based on information theory and fact that both position and frequency of repeated sequences are not expected to occur with the identical presence in a random sequence of the same length. The second method includes building signatures of biological sequences and profiles of taxonomic classes based on repetitive parts of sequences and distances between these repeats. Proposed methods have been validated on multiple data sets and compared with results obtained using different well known and accepted methods in this field like BLAST, Clustal Omega and methods based on k-mers. Resulted precision for proposed methods is close to values provided for existing methods for the majority of tested data-sets, and time performance depends strictly to used infrastructure and sequence type. Methods provide results that are comparable with other commonly used methods focused on resolving the same problem, taking into consideration statistically significant repetitive parts of sequences with different characteristics.