Algoritmi kombinatorne optimizacije za (pseudo)poravnavanje u bioinformatici

The field of bioinformatics is a fast growing interdisciplinary field with a strong contribution from mathematics and computer science. This thesis will deal with mathematical problems and algorithmic challenges from that field. Its first focus will be the comparison of hierarchic structures, mainly phylogenetic trees, which is used to explain various biological processes such as the evolution of the species. We will study mathematical models and algorithmic techniques which quantify the distance between such structures as means of determining the similarities or dissimilarities between them. The focus will be given to formulating the problem based on matching in the context of integer linear programming. Our goal will be to find a novel solution which respects the ancestry relations defined by those hierarchical structures and is often overlooked in the current research. Our main result will be given in a form of a software tool - Trajan, which will be tested on both the real world and simulated data. The second focus of the thesis will come from the problem of sequencing the RNA molecule. It is a combinatorial process of reconstruction of the RNA molecule from short nucleotide sequences which is used to analyze the transcriptome of a biological sample. Many recent studies consider a problem of quantification and classification of unannotated splicing events which often occur due to the mutations caused by abnormal state of the organism, e.g. cancer. We will present another software tool, called fortuna, which brings together high accuracy and fast running times to the analysis of the alternative splicing events unlike any of the well established competitor tools.Bioinformatika je interdisciplinarno područje koje spaja matematiku, računalnu znanost, biologiju, medicinu i inženjerske discipline s ciljem razvijanja matematičkih modela i algoritamskih tehnika koje pružaju uvid u mnoge biološke procese kao što su transkripcija i sinteza proteina unutar stanice ili evolucija, ali i genetske osnove bolesti i adaptacija, razlike i interakcija među jedinkama i populacijama i sl. Počelo se razvijati ranih 50-tih godina prošlog stoljeća uvođenjem računala u obradu podataka dobivenih sekvenciranjem proteina [28] koje su po prvi puta prikupili [88][89]. U ovoj disertaciji, bavimo se problematikom iz tog područja. Naš prvi fokus je usporedba hijerarhijskih struktura, najviše filogenetskih stabala koja organiziraju biološke vrste u stablastu strukturu baziranu na evoluciji. Njihovi čvorovi mogu predstavljati i druge podatke kao što su podklonovi tumora nastali prilikom evolucije tumora [54]. Također, protein-protein interakcijske (PPI) mreže implicitno sadrže hijerarhijske strukture koje je moguće rekonstruirati koristeći se hijerarhijskim metodama klasteriranja [37]. Uspoređivanje filogenetskih stabala dobivenih različitim metodama rekonstrukcije može kvantificirati njihove sličnosti i pružiti uvid u simbiozu parazita i domaćina [51]. Najpopularnija udaljenost među stablima je Robinson-Fouldsova udaljenost [85] u pozadini koje leži sparivanje vrhova dva stabla čija su podstabla topološki identična. Moguće ju je efikasno izračunati u polinomnom vremenu, no ona pruža ograničen uvid “niske razlučivosti” u razlike između dva stabla. Nadalje, često nije u mogućnosti identificirati topološki slične strukture te je izrazito osjetljiva na vrlo male promjene u ulaznim podacima [17][71]. Naše istraživanje direktno se nadovezuje na [7] u kojem je predstavljena generalizacija Robinson-Fouldsove udaljenosti čiji je glavni cilj otklanjanje njezinih loših svojstava putem izračuna bijektivnog preslikavanja vrhova iz jednog stabla u drugo koje poštuje roditeljske odnose. Postoje i druge udaljenosti definirane među stablima od kojih neke [24][71][63][11][12] imaju loša svojstva ili su u praksi teške za izračunati [2]. Unatoč tome što je u [7] dokazano da je izračun generalizirane Robinson-Fouldsove udaljenosti NP-težak problem, u [45] je pokazano kako postoji efikasno rješenje za njezin izračun koje se bazira na paradigmi cjelobrojnog linearnog programiranja. Naš glavni znanstveni doprinos je definicija uvjeta koji uvelike smanjuju poliedar u kojem rješavač Trajan metodom grananja-i-rezanja traži optimalno rješenje. Ideja na kojoj se temelje naši uvjeti je pronalaženje skupa bridova između dva stabla koji maksimalno narušavaju roditeljske odnose metodom dinamičkog programiranja čiju dinamičku tablicu efikasno popunjavamo prolaženjem vrhovima stabala. Smatramo da dva brida (x1;y1);(x2;y2) ne narušavaju roditeljske odnose ukoliko vrijedi da je x1 predak od x2 u prvom stablu ako i samo ako je y1 predak od y2 u drugom stablu. Trajan smo testirali na simuliranim stablima iz uniformnog i Yuleovog modela [9], te na stvarnim filogenetskim stablima kojima je predočena evolucija zelenih algi [69] i biljka cvijetnjača [92]. U drugom dijelu ove disertacije bavimo se problemima koji dolaze iz područja sekvenciranja molekule RNA (RNA-Seq). To je postupak čitanja strukture molekule RNA u obliku kratkih lanaca nukleotida sastavljenih od molekula adenina, citozina, gvanina i timina u svrhu određivanja svojstava stanične molekule DNA koja sadrži genetske informacije instrumentalne za proces nasljeđivanja. Tijekom posljednjih dvadesetak godina, tehnologija za sekvenciranje molekule RNA se razvijala iznimno brzo. Metode koje sekvenciraju čitav ljudski genom unutar jednoga dana česta su pojava. Podatke dobivene sekvenciranjem (u obliku kratkih lanaca nukleotida) potrebno je poravnati s referentnim genomom, tj. odrediti mjesto u genomu s kojega je pročitan podatak, a za što se koriste specijalizirani računalni programi kao što su [32][66][67][14][78][94][96][39][53]. Kvantifikacija količine podataka ovisno o njihovoj lokaciji u genomu je važan proces koji nam daje uvid u stanje organizma čiji smo genetski materijal sekvencirali. Za istraživanja bolesti poput raka [48] ili autizma [38] od iznimne su važnosti oni lanci nukleotida koji su sekvencirani s mutiranih područja. Identifikacija i kvantifikacija tih podataka najčešće se vrši nakon poravnjavanja na referentni genom pomoću specijaliziranog softvera kao što je [62], čije je izvršavanje dugotrajno u praksi, ili pomoću heurističkih metoda niske preciznosti [96]. Naš doprinos u ovome području je efikasan i precizan program: fortuna. On pridružuje kratke lance nukleotida klasama ekvivalencije konstruirane na temelju proširene reference koja omogućuje identifikaciju i klasifikaciju do sada nepoznatih izrezivanja (alternativnih načina prepisivanja molekule DNA koji prethode sintezi proteina). Proces koji fortuna izvršava može se podijeliti u tri koraka: gradnja indeksa, poravnavanje i naknadna obrada. U prvom koraku fortuna nadopunjuje referentni genom koristeći jedan od tri dobro definirana skupa mogućih izrezivanja. Potom slijedi proces poravnavanja podataka dobivenih sekvenciranjem na prošireni referentni genom. U koraku naknadne obrade vrši se najbitniji proces dodjeljivanja podataka klasama ekvivalencije. Rezultate na simuliranim i stvarnim podacima usporedili smo s onima dobivenim pomoću nekoliko konkurentnih programa