Combinatorial methods in comparative genomics

by Eriksen, Niklas

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, circular permutations, and evolutionary operations like reversals (reversing the order of a segment of genes) and transpositions (moving a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the breakpoint distance and the reversal distance. We have in this thesis applied combinatorics to several important problems, leading to these results: • An algorithm for computing, within any factor 1+? > 1, the minimal number of reversals and transpositions, the latter double-counted for certain reasons, needed to transform one gene order permutation into another. • A good approximative formula for the expected number of reversals between two gene order permutations with b breakpoints between them: ( b log 1 ? n(1? tappr(b) = 1 2n?2 ) ) log (1 ? 2 ) . n • A formula for the expected transposition distance in an ordinary permutation given by t random transpositions. The inverse is an estimate of the expected evolutionary distance between two gene order permutations, given their reversal distance. • A new approach for computing the expected evolutionary distance, with a conjecture regarding which gene order permutations are comparable. • A formula for the expected number of inversions in a permutation generated by t random adjacent transpositions. • An analysis of the heuristic Derange for computing the weighted distance between two gene order permutations, showing that it is reliable if the right weights are used, and an extension of Derange that addresses the median problem. Using this extension, we have devised a fast algorithm for computing evolutionary trees that match other, slower, algorithms. ISBN 91-7283-477-3 • TRITA-MAT-03-MA-06 • ISSN 1401-2294 • ISRN KTH/MAT/DA--03/01--SE iii iv Sammanfattning Analys av genordning i organismer har visat sig vara ett kraftfullt verktyg för först?a de evolutionära processerna och för att ta reda p?a hur olika arter är släkt med varandra. Vi kan ofta formulera fr?ageställningar inom detta omr?ade med kombinatoriska termer. Ett genom kan ses som en tecknad, cirkulär permutation av gener, och evolutionära processer som vändningar (ett segment av gener ges omvänd ordning) och transpositioner (ett segment av gener flyttas) kan beskrivas enkelt med kombinatorik. En vanlig fr?ageställning rör det evolutionära avst?andet mellan tv?a arter. Det finns flera kombinatoriska avst?andsfunktioner som ger bra uppskattningar av detta avst?and. Exempel p?a s?adana är brytpunktsavst?andet och vändningsavst?andet. I denna avhandling har vi tillämpat kombinatoriska metoder p?a flera viktiga problem, vilket gett följande resultat: • En algoritm för att inom varje faktor 1 + ? > 1 beräkna det minsta antalet vändningar och transpositioner, de senare av goda skäl räknade dubbelt, som behövs för att omvandla en permutation av gener till en annan. • En god approximation av det förväntade antalet vändningar mellan tv?a permutationer av gener p?a brytpunktsavst?and b: ( b log 1 ? n(1? tappr(b) = 1 2n?2 ) ) log (1 ? 2 ) . n • En formel för det förväntade antalet transpositioner vi maximalt kan förkorta en produkt av t slumpmässigt valda transpositioner till. Inversen till denna funktion ger en uppskattning av det förväntade evolutionära avst?andet mellan tv?a permutationer av gener, som funktion av deras vändningsavst?and. • Ett nytt sätt att angripa det förväntade evolutionära avst?andet, samt en förmodan som berör vilka permutationer av gener som är jämförbara. • En formel för det förväntade inversionstalet i en permutation som skapats med hjälp av t slumpmässigt valda granntranspositioner. • Vi har analyserat den avst?andsberäknande heuristiken Derange, och visat att den är tillförlitlig om rätt vikter används. Genom att utnyttja en utökning av Derange som beräknar medianen av tre permutationer av gener har vi utformat en algoritm för att beräkna evolutionära träd. Denna algoritm är jämförelsevis snabb, och mäter sig väl med andra l?angsammare algoritmer. ISBN 91-7283-477-3 • TRITA-MAT-03-MA-06 • ISSN 1401-2294 • ISRN KTH/MAT/DA--03/01--SE v vi