title: Improving reversal median computation using commuting reversals and cycle information.
abstract: In the past decade, genome rearrangements have attracted increasing attention from both biologists and computer scientists as a new type of data for phylogenetic analysis. Methods for reconstructing phylogeny from genome rearrangements include distance-based methods, MCMC methods, and direct optimization methods. The latter, pioneered by Sankoff and extended with the software suites GRAPPA and MGR, is the most accurate approach, but is very limited due to the difficulty of its scoring procedure--it must solve multiple instances of the reversal median problem to compute the score of a given tree. The reversal median problem is known to be NP-hard and all existing solvers are extremely slow when the genomes are distant. In this paper, we present a new reversal median heuristic for unichromosomal genomes. The new method works by applying sets of reversals in a batch where all such reversals both commute and do not break the cycle of any other. Our testing using simulated datasets shows that this method is much faster than the leading solver for difficult datasets with only a slight accuracy penalty, yet retains better accuracy than other heuristics with comparable speed, and provides the additional option of searching for multiple medians. This method dramatically increases the speed of current direct optimization methods and enables us to extend the range of their applicability to organellar and small nuclear genomes with more than 50 reversals along each edge.
authors.affiliation: Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA.
authors.forename: William
authors.initials: W
authors.lastname: Arndt
authors.forename: Jijun
authors.initials: J
authors.lastname: Tang
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D016678:Genome; D008957:Models, Genetic; D010802:Phylogeny; D012984:Software
references.citation: Genome Biol. 2007;8(11):R236
references.pmid: 17996033
references.citation: Proc Natl Acad Sci U S A. 2003 Jun 24;100(13):7672-7
references.pmid: 12810957
references.citation: Mol Biol Evol. 1987 Jul;4(4):406-25
references.pmid: 3447015
references.citation: J Comput Biol. 1998 Fall;5(3):555-70
references.pmid: 9773350
references.citation: Genome Res. 2002 Jan;12(1):26-36
references.pmid: 11779828
references.citation: Mol Biol Evol. 2005 Jun;22(6):1456-67
references.pmid: 15772379
references.citation: J Comput Biol. 2003;10(3-4):575-97
references.pmid: 12935346
references.citation: J Comput Biol. 2001;8(5):483-91
references.pmid: 11694179
references.citation: Pac Symp Biocomput. 2001;:583-94
references.pmid: 11262975
references.citation: Bioinformatics. 2007 Jan 15;23(2):e129-35
references.pmid: 17237080
references.citation: Genome Inform Ser Workshop Genome Inform. 1997;8:25-34
references.pmid: 11072302
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2008 Jul-Sep;5(3):348-56
references.pmid: 18670039