Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Combinatorics of genome rearrangements and phylogeny
KTH, Superseded Departments, Mathematics.
2001 (English)Licentiate thesis, monograph (Other scientific)
Abstract [en]

This thesis deals with combinatorial problems taken frombioinformatics. In particular, we study the problem ofinferring distances between bacterial species by looking attheir respective gene orders. We regard one of the gene ordersas a permutation of the other. Given a set of valid operations,we seek the most parsimonious way to sort this permutation. Wealso look at the more complex problem of combining a set ofspecies into a phylogenetic tree, which shows the relationshipsbetween all species.The computer program Derange II by Blanchette andSanko® uses a greedy algorithm to estimate theevolutionary distance between two species. The success dependson a set of weights, which may be specified by the user. Wehave examined which weights are optimal, and also the qualityof this program using optimal weights.Derange II has been extended to solve the medianproblem, that is finding the permutation that is closest tothree other permutations. We then use this new version to buildphylogenetic trees directly from gene order permutations. Insome situations, this new method works much better thanprevious methods.There is an analytical expression for the evolutionarydistance between two species if the set of allowed operationsincludes only inversions (reversing a segment of genes).Allowing transpositions (swapping two adjacent segments) aswell, we have found a (1+")-approximation for this distance,where we have weighted the di®erent operations accordingto our results on the Derange II weights.

Place, publisher, year, edition, pages
Stockholm: Matematik , 2001. , viii, 43 p.
Series
Trita-MAT, ISSN 1401-2286 ; 2001:06
Identifiers
URN: urn:nbn:se:kth:diva-1499OAI: oai:DiVA.org:kth-1499DiVA: diva2:7400
Note
NR 20140805Available from: 2002-10-23 Created: 2002-10-23Bibliographically approved

Open Access in DiVA

fulltext(884 kB)332 downloads
File information
File name FULLTEXT01.pdfFile size 884 kBChecksum MD5
c0ccaabcab92a0f40e44ee84db3f2f757757ea0f624bed0f527ebfe8bd6ec0452a52ed7b
Type fulltextMimetype application/pdf

By organisation
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 332 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 388 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf