The infinite sites model of genome evolution.
We formalize the problem of recovering the evolutionary history of a set of genomes that are related to an unseen common ancestor genome by operations of speciation, deletion, insertion, duplication, and rearrangement of segments of bases. The problem is examined in the limit as the number of bases in each genome goes to infinity. In this limit, the chromosomes are represented by continuous circles or line segments. For such an infinite-sites model, we present a polynomial-time algorithm to find the most parsimonious evolutionary history of any set of related present-day genomes.
Ma
Jian
J
Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064, USA.
Ratan
Aakrosh
A
Raney
Brian J
BJ
Suh
Bernard B
BB
Miller
Webb
W
Haussler
David
D
D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D019143:Evolution, Molecular; D016678:Genome; D006801:Humans; D051379:Mice; D008957:Models, Genetic; D009154:Mutation / Q000235:genetics; D014960:X Chromosome
Mol Cell Biol. 1996 May;16(5):2164-73
8628283
Bioinformatics. 2004 Aug 4;20 Suppl 1:i265-73
15262808
Genetics. 1969 Apr;61(4):893-903
5364968
Trends Genet. 2000 May;16(5):227-31
10782117
Proc Natl Acad Sci U S A. 2006 Dec 26;103(52):19824-9
17189424
Theor Popul Biol. 1983 Apr;23(2):183-201
6612631
Bioinformatics. 1999 Nov;15(11):909-17
10743557
J Comput Biol. 2005 Jul-Aug;12(6):812-21
16108718
Syst Zool. 1970 Jun;19(2):99-113
5449325
Genome Res. 2002 Jan;12(1):26-36
11779828
Mol Cell Biol. 1986 Dec;6(12):4295-304
3025650
Genome Res. 2007 Apr;17(4):413-21
17322288
Annu Rev Genet. 1998;32:619-97
9928494
Genome Res. 2006 Dec;16(12):1557-65
16983148
J Mol Evol. 1980 Dec;16(2):111-20
7463489
Bioinformatics. 2005 Aug 15;21(16):3340-6
15951307
Annu Rev Genet. 2004;38:645-79
15568989
PLoS Comput Biol. 2007 Nov;3(11):e209
17997591
Science. 2005 Jul 22;309(5734):613-7
16040707
J Theor Biol. 1977 Jan 21;64(2):199-213
839800
Science. 2003 Aug 8;301(5634):793-7
12907789
J Mol Evol. 1985;22(2):160-74
3934395
Nature. 2007 May 10;447(7141):167-77
17495919
Genome Res. 2005 Jan;15(1):98-110
15590940
Nature. 2008 May 1;453(7191):56-64
18451855
Genome Res. 2003 Jan;13(1):103-7
12529312
J Comput Biol. 2008 Oct;15(8):1007-27
18774902
Pac Symp Biocomput. 2001;:583-94
11262975