On reversal and transposition medians
Bericht
Autoren
Bader, Martin
Fakultäten
Fakultät für Ingenieurwissenschaften und InformatikUlmer Schriftenreihe
Ulmer Informatik-Berichte
Zusammenfassung
During the last years, the genomes of more and more species have been sequenced, providing data for phylogenetic reconstruction based on genome rearrangement measures. A main task in all phylogenetic reconstruction algorithms is to solve the median of three problem. Although this problem is NP-hard even for the simplest distance measures, there are exact algorithms for the breakpoint median and the reversal median that are fast enough for practical use. In this paper, we extend this approach to the transposition median as well as to the weighted reversal and transposition median. Although there is no exact polynomial algorithm known even for the pairwise distances, we will show that it is in most cases possible to solve these problems exactly within reasonable time by using a branch and bound algorithm.
Erstellung / Fertigstellung
2009
Normierte Schlagwörter
Genomprojekt [GND]Translocation: Genetics [LCSH]
Schlagwörter
Comparative genomics; Genome rearrangements; Median; Reversals; TranspositionsDDC-Sachgruppe
DDC 004 / Data processing & computer scienceMetadata
Zur LanganzeigeZitiervorlage
Bader, Martin (2009): On reversal and transposition medians. Open Access Repositorium der Universität Ulm. http://dx.doi.org/10.18725/OPARU-1041