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.