Algorithms for Efficient Alignment-Free Sequence Comparison

doctoral thesis

• Title (english): Algoritmi za učinkovitu usporedbu sekvenci bez korištenja sravnjivanja
• Author: Mirjana Domazet Lošo
• Mentor: Strahil Ristov (komentor)
• Mentor: Bernhard Haubold (komentor); strani drzavljanin: Nije dostupno
• Committee member: Damir Kalpić (predsjednik povjerenstva)
• Committee member: Bernhard Haubold (član povjerenstva); strani drzavljanin: Nije dostupno
• Committee member: Strahil Ristov (član povjerenstva)
• Committee member: Mirta Baranović (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Applied Computing); Zagreb
• Defense date and country: 2010-10-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing; Data Processing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Sequence comparison is an essential tool in modern biology. It is used to identify homologous regions between sequences, and to detect evolutionary relationships between organisms. Sequence comparison is usually based on alignments. However, aligning whole genomes is computationally difficult. As an alternative approach, alignment-free sequence comparison can be used. In my thesis, I concentrate on two problems that can be solved without alignment: (i) estimation of substitution rates between nucleotide sequences, and (ii) detection of local sequence homology. In the first part of my thesis, I developed and implemented a new algorithm for the efficient alignment-free computation of the number of nucleotide substitutions per site, and applied it to the analysis of large data sets of complete genomes. In the second part of my thesis, I developed and implemented a new algorithm for detecting matching regions between nucleotide sequences. I applied this solution to the classification of circulating recombinant forms of HIV, and to the analysis of bacterial genomes subject to horizontal gene transfer.

Abstract (english)

Uspoređivanje sekvenci je osnovni alat u modernoj biologiji, a koristi se za pronalaženje homolognih dijelova između sekvenci te za otkrivanje evolucijskih odnosa između organizama. Uspoređivanje je sekvenci obično temeljeno na sravnjivanju. Međutim, sravnjivanje cijelih genoma je računalno zahtijevan postupak. Kao alternativni pristup, mogu se koristiti metode koje ne koriste sravnjivanje sekvenci. U sklopu svoje doktorske disertacije, koristila sam pristup koji ne zahtijeva sravnjivanje sekvenci u rješavanju dvaju problema: (i) procjena brzine supstitucije između nukleotidnih sekvenci; (ii) određivanje lokalne homologije između nukleotidnih sekvenci. U sklopu prvog dijela disertacije razvila sam i implementirala algoritam za učinkovito računanje procjene relativnog broja supstitucija između dviju nukleotidnih sekvenci bez korištenja sravnjivanja, koji sam primijenila za analizu velikih skupova cijelih genoma. U drugom dijelu disertacije razvila sam i implementirala novi algoritam za određivanje jednakih dijelova između nukleotidnih sekvenci. Rješenje sam primijenila za određivanje roditeljskih tipova rekombinantnih oblika virusa HIV te za analizu bakterijskih genoma pod utjecajem horizontalnog prijenosa gena.

• Keywords: alignment-free method; evolutionary distance; local sequence homology; genome comparison; HIV; horizontal gene transfer; suffix tree; suffix array; shortest unique substring
• Keywords (english): usporedbe sekvenci bez sravnjivanja; lokalna homologija; evolucijska udaljenost; usporedba genoma; HIV; horizontalni prijenos gena; sufiksno stablo; sufiksno polje; najkraći jedinstveni podniz.
• Language: english
• URN:NBN: urn:nbn:hr:168:377942
• Project: Number: 036-0361983-2012; Title: Semantička integracija heterogenih izvorišta podataka; Leader: Mirta Baranović; Jurisdiction: Croatia; Funder: MZOS; Funding stream: ZP
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Catalog URL: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=34298
• Type of resource: Text
• Extent: 127 str. ; 30 cm.
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-20 12:22:53