A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions Export

@article{martin:reversals, abstract = {Background:\&\#10;Due to recent progress in genome sequencing, more and more data for phylogenetic reconstruction based on rearrangement distances between genomes become available. However, this phylogenetic reconstruction is a very challenging task: For the most simple distance measures (the breakpoint distance and the reversal distance), the problem is NP-hard even if one considers only three genomes.\&\#10;Results:\&\#10;In this paper, we present a new heuristic algorithm that directly constructs a phylogenetic tree with respect to the weighted reversal and transposition distance. Experimental results on previously published datasets show that constructing phylogenetic trees in this way results in better trees than constructing the trees with respect to the reversal distance, and recalculating the weight of the trees with the weighted reversal and transposition distance. \&\#10;Conclusions:\&\#10;The possibility of creating phylogenetic trees directly with respect to the weighted reversal and transposition distance results in biologically more realistic scenarios. Our algorithm can solve today's most challenging biological datasets in a reasonable amount of time.}, author = {Martin and Ohlebusch, Enno}, citeulike-article-id = {3747525}, citeulike-linkout-0 = {http://dx.doi.org/10.1186/1471-2105-9-516}, day = {04}, doi = {10.1186/1471-2105-9-516}, issn = {1471-2105}, journal = {BMC Bioinformatics}, keywords = {breakpoints, rearrangement, reconstruction}, month = {December}, pages = {516+}, posted-at = {2008-12-04 21:08:59}, priority = {2}, title = {A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions}, url = {http://dx.doi.org/10.1186/1471-2105-9-516}, volume = {9}, year = {2008} }

TY - JOUR ID - martin:reversals L3 - citeulike-article-id:3747525 N2 - Background:
Due to recent progress in genome sequencing, more and more data for phylogenetic reconstruction based on rearrangement distances between genomes become available. However, this phylogenetic reconstruction is a very challenging task: For the most simple distance measures (the breakpoint distance and the reversal distance), the problem is NP-hard even if one considers only three genomes.
Results:
In this paper, we present a new heuristic algorithm that directly constructs a phylogenetic tree with respect to the weighted reversal and transposition distance. Experimental results on previously published datasets show that constructing phylogenetic trees in this way results in better trees than constructing the trees with respect to the reversal distance, and recalculating the weight of the trees with the weighted reversal and transposition distance. 
Conclusions:
The possibility of creating phylogenetic trees directly with respect to the weighted reversal and transposition distance results in biologically more realistic scenarios. Our algorithm can solve today's most challenging biological datasets in a reasonable amount of time. JF - BMC Bioinformatics SN - 1471-2105 TI - A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions VL - 9 SP - 516 KW - breakpoints KW - rearrangement KW - reconstruction AU - Martin AU - Ohlebusch, Enno PY - 2008/12/04/ UR - http://dx.doi.org/10.1186/1471-2105-9-516 ER -