DUPCAR: reconstructing contiguous ancestral regions with duplications.
Accurately reconstructing the large-scale gene order in an ancestral genome is a critical step to better understand genome evolution. In this paper, we propose a heuristic algorithm, called DUPCAR, for reconstructing ancestral genomic orders with duplications. The method starts from the order of genes in modern genomes and predicts predecessor and successor relationships in the ancestor. Then a greedy algorithm is used to reconstruct the ancestral orders by connecting genes into contiguous regions based on predicted adjacencies. Computer simulation was used to validate the algorithm. We also applied the method to reconstruct the ancestral chromosome X of placental mammals and the ancestral genomes of the ciliate Paramecium tetraurelia.
Ma
Jian
J
Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064, USA. jianma@soe.ucsc.edu
Ratan
Aakrosh
A
Raney
Brian J
BJ
Suh
Bernard B
BB
Zhang
Louxin
L
Miller
Webb
W
Haussler
David
D
D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D019143:Evolution, Molecular; D020440:Gene Duplication; D016678:Genome; D006801:Humans; D008957:Models, Genetic; D016805:Paramecium tetraurelia / Q000235:genetics; D010802:Phylogeny
Genome Res. 2003 Jan;13(1):37-45
12529304
Genome Res. 2006 Dec;16(12):1557-65
16983148
Mol Phylogenet Evol. 1996 Oct;6(2):189-213
8899723
Genome Res. 2006 Mar;16(3):311-3
16510896
J Comput Biol. 2000;7(3-4):429-47
11108472
Nature. 2006 Nov 9;444(7116):171-8
17086204
Genome Res. 2006 Dec;16(12):1441-4
17053088
Genome Res. 2003 Jan;13(1):103-7
12529312
Evol Bioinform Online. 2007 Feb 21;2:295-302
19455223
Bioinformatics. 1999 Nov;15(11):909-17
10743557
Pac Symp Biocomput. 2001;:583-94
11262975
Genome Res. 2006 Mar;16(3):306-10
16510895
Proc Natl Acad Sci U S A. 1998 Apr 14;95(8):4447-52
9539757
Genome Res. 2007 Dec;17(12):1932-42
17989260
Genome Res. 2002 Jan;12(1):26-36
11779828
Proc Natl Acad Sci U S A. 1984 Feb;81(3):814-8
6583681
Science. 2005 Jul 22;309(5734):613-7
16040707
Science. 2003 Aug 8;301(5634):793-7
12907789
Trends Genet. 2000 May;16(5):227-31
10782117
J Comput Biol. 1998 Fall;5(3):555-70
9773350