title: Ancestral genome inference using a genetic algorithm approach.
abstract: Recent advancement of technologies has now made it routine to obtain and compare gene orders within genomes. Rearrangements of gene orders by operations such as reversal and transposition are rare events that enable researchers to reconstruct deep evolutionary histories. An important application of genome rearrangement analysis is to infer gene orders of ancestral genomes, which is valuable for identifying patterns of evolution and for modeling the evolutionary processes. Among various available methods, parsimony-based methods (including GRAPPA and MGR) are the most widely used. Since the core algorithms of these methods are solvers for the so called median problem, providing efficient and accurate median solver has attracted lots of attention in this field. The "double-cut-and-join" (DCJ) model uses the single DCJ operation to account for all genome rearrangement events. Because mathematically it is much simpler than handling events directly, parsimony methods using DCJ median solvers has better speed and accuracy. However, the DCJ median problem is NP-hard and although several exact algorithms are available, they all have great difficulties when given genomes are distant. In this paper, we present a new algorithm that combines genetic algorithm (GA) with genomic sorting to produce a new method which can solve the DCJ median problem in limited time and space, especially in large and distant datasets. Our experimental results show that this new GA-based method can find optimal or near optimal results for problems ranging from easy to very difficult. Compared to existing parsimony methods which may severely underestimate the true number of evolutionary events, the sorting-based approach can infer ancestral genomes which are much closer to their true ancestors. The code is available at http://phylo.cse.sc.edu.
authors: Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America.
authors: Nan
authors: N
authors: Gao
authors: Ning
authors: N
authors: Yang
authors: Jijun
authors: J
authors: Tang
mesh_terms: D000465:Algorithms; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic; D009154:Mutation; D010802:Phylogeny
references: Bioinformatics. 2005 Aug 15;21(16):3340-6
references: 15951307
references: Proc Natl Acad Sci U S A. 2003 Jun 24;100(13):7672-7
references: 12810957
references: BMC Cancer. 2006 Jun 16;6:159
references: 16780590
references: Biochim Biophys Acta. 2005 Aug 30;1725(1):19-29
references: 15990235
references: Genome Res. 2005 Jan;15(1):1-18
references: 15632085
references: Pac Symp Biocomput. 2001;:583-94
references: 11262975
references: BMC Bioinformatics. 2012;13 Suppl 19:S5
references: 23281922
references: Science. 1992 Mar 27;255(5052):1697-9
references: 17749424
references: BMC Bioinformatics. 2009 Apr 22;10:120
references: 19386099
references: J Comput Biol. 1998 Fall;5(3):555-70
references: 9773350
references: J Mol Biol. 1993 May 5;231(1):75-81
references: 8496967
references: Genome Res. 2002 Jan;12(1):26-36
references: 11779828