title: Probabilistic phylogenetic inference with insertions and deletions.
abstract: A fundamental task in sequence analysis is to calculate the probability of a multiple alignment given a phylogenetic tree relating the sequences and an evolutionary model describing how sequences change over time. However, the most widely used phylogenetic models only account for residue substitution events. We describe a probabilistic model of a multiple sequence alignment that accounts for insertion and deletion events in addition to substitutions, given a phylogenetic tree, using a rate matrix augmented by the gap character. Starting from a continuous Markov process, we construct a non-reversible generative (birth-death) evolutionary model for insertions and deletions. The model assumes that insertion and deletion events occur one residue at a time. We apply this model to phylogenetic tree inference by extending the program dnaml in phylip. Using standard benchmarking methods on simulated data and a new "concordance test" benchmark on real ribosomal RNA alignments, we show that the extended program dnamlepsilon improves accuracy relative to the usual approach of ignoring gaps, while retaining the computational efficiency of the Felsenstein peeling algorithm.
authors.affiliation: Janelia Farm Research Campus, Howard Hughes Medical Institute, Ashburn, Virginia, United States of America. rivase@janelia.hhmi.org
authors.forename: Elena
authors.initials: E
authors.lastname: Rivas
authors.forename: Sean R
authors.initials: SR
authors.lastname: Eddy
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D004247:DNA / Q000235:genetics; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D015233:Models, Statistical; D016254:Mutagenesis, Insertional; D010802:Phylogeny; D016012:Poisson Distribution; D012335:RNA, Ribosomal / Q000235:genetics; D016415:Sequence Alignment / Q000706:statistics & numerical data*; D017384:Sequence Deletion; D012984:Software
chemical_list: D012335:RNA, Ribosomal; D004247:DNA
references.citation: BMC Evol Biol. 2004 Sep 17;4:33
references.pmid: 15377393
references.citation: J Mol Evol. 1991 Aug;33(2):114-24
references.pmid: 1920447
references.citation: BMC Bioinformatics. 2005 Apr 01;6:83
references.pmid: 15804354
references.citation: Mol Biol Evol. 2004 Mar;21(3):419-27
references.pmid: 14660689
references.citation: Proteins. 2003 Aug 15;52(3):446-53
references.pmid: 12866055
references.citation: Mol Biol Evol. 2001 May;18(5):691-9
references.pmid: 11319253
references.citation: BMC Bioinformatics. 2006 Jun 08;7:292
references.pmid: 16762073
references.citation: J Comput Biol. 2004;11(2-3):413-28
references.pmid: 15285899
references.citation: Biometrics. 1995 Mar;51(1):100-13
references.pmid: 7766767
references.citation: Methods Enzymol. 1996;266:198-212
references.pmid: 8743686
references.citation: J Mol Evol. 1980 Dec;16(2):111-20
references.pmid: 7463489
references.citation: Bioinformatics. 2007 Feb 1;23(3):289-97
references.pmid: 17110370
references.citation: J Mol Evol. 1999 Jul;49(1):11-22
references.pmid: 10368429
references.citation: Mol Biol Evol. 1996 Jan;13(1):93-104
references.pmid: 8583911
references.citation: Mol Biol Evol. 2004 Mar;21(3):529-40
references.pmid: 14694074
references.citation: BMC Bioinformatics. 2004 Oct 26;5:166
references.pmid: 15507142
references.citation: J Mol Evol. 1985;22(2):160-74
references.pmid: 3934395
references.citation: Bioinformatics. 1999 Jun;15(6):446-54
references.pmid: 10383470
references.citation: Bioinformatics. 2003;19 Suppl 1:i147-57
references.pmid: 12855451
references.citation: Syst Biol. 2005 Aug;54(4):548-61
references.pmid: 16085574
references.citation: J Mol Evol. 1981;17(6):368-76
references.pmid: 7288891
references.citation: Bull Math Biol. 1989;51(1):79-94
references.pmid: 2706403
references.citation: BMC Bioinformatics. 2005 Mar 21;6:63
references.pmid: 15780137
references.citation: BMC Bioinformatics. 2005 Sep 27;6:236
references.pmid: 16188037
references.citation: J Comput Biol. 2003;10(6):869-89
references.pmid: 14980015
references.citation: Bioinformatics. 2004 Aug 12;20(12):1850-60
references.pmid: 14988105
references.citation: Comput Biol Chem. 2004 Jul;28(3):219-26
references.pmid: 15261152
references.citation: Genome Res. 2005 Aug;15(8):1034-50
references.pmid: 16024819
references.citation: Mol Biol Evol. 1996 Jan;13(1):105-14
references.pmid: 8583885
references.citation: Bioinformatics. 2001 Aug;17(8):754-5
references.pmid: 11524383
references.citation: Bioinformatics. 2001 Sep;17(9):803-20
references.pmid: 11590097
references.citation: J Mol Biol. 2004 Aug 6;341(2):617-31
references.pmid: 15276848
references.citation: Syst Biol. 2006 Oct;55(5):756-68
references.pmid: 17060197
references.citation: Bioinformatics. 2003 Jan 22;19(2):219-27
references.pmid: 12538242
references.citation: Biometrics. 1999 Mar;55(1):1-12
references.pmid: 11318142
references.citation: Bioinformatics. 2004 Aug 4;20 Suppl 1:i94-100
references.pmid: 15262786
references.citation: Mol Biol Evol. 1998 Dec;15(12):1600-11
references.pmid: 9866196
references.citation: J Mol Evol. 1996 Sep;43(3):304-11
references.pmid: 8703097
references.citation: Bioinformatics. 2003 Mar 1;19(4):490-9
references.pmid: 12611804
references.citation: Proteins. 2001 Oct 1;45(1):102-4
references.pmid: 11536366
references.citation: J Mol Evol. 1994 Jul;39(1):105-11
references.pmid: 8064867
references.citation: Bioinformatics. 2004 Sep 22;20(14):2175-80
references.pmid: 15044240
references.citation: J Mol Evol. 1992 Jan;34(1):3-16
references.pmid: 1556741
references.citation: J Mol Biol. 2000 Sep 8;302(1):265-79
references.pmid: 10964574
references.citation: Syst Biol. 2003 Oct;52(5):696-704
references.pmid: 14530136
references.citation: Proc Natl Acad Sci U S A. 1955 Jun 15;41(6):387-91
references.pmid: 16589686
references.citation: Genetics. 2000 May;155(1):431-49
references.pmid: 10790415
references.citation: Proc Natl Acad Sci U S A. 2004 Sep 28;101(39):13994-4001
references.pmid: 15292512
references.citation: Comput Appl Biosci. 1997 Oct;13(5):555-6
references.pmid: 9367129
references.citation: Genetics. 1995 Feb;139(2):993-1005
references.pmid: 7713447
references.citation: J Theor Biol. 2004 May 7;228(1):97-106
references.pmid: 15064085
references.citation: Genome Res. 2004 Mar;14(3):442-50
references.pmid: 14993209
references.citation: Proc Natl Acad Sci U S A. 2003 Dec 9;100(25):14960-5
references.pmid: 14657378
references.citation: Bioinformatics. 1998;14(2):157-63
references.pmid: 9545448
references.citation: Pac Symp Biocomput. 2001;:179-90
references.pmid: 11262938
references.citation: J Bioinform Comput Biol. 2006 Jun;4(3):721-44
references.pmid: 16960972
references.citation: Bioinformatics. 2005 Feb 15;21(4):456-63
references.pmid: 15608047
references.citation: Mol Biol Evol. 1994 May;11(3):459-68
references.pmid: 8015439
references.citation: J Mol Biol. 1996 Oct 25;263(2):196-208
references.pmid: 8913301
references.citation: Mol Biol Evol. 2001 Apr;18(4):481-90
references.pmid: 11264399
references.citation: Genome Res. 2004 Dec;14(12):2412-23
references.pmid: 15574820
references.citation: J Mol Biol. 2003 Oct 17;333(2):453-60
references.pmid: 14529629
references.citation: BMC Bioinformatics. 2002;3:2
references.pmid: 11869452
references.citation: Bioinformatics. 1998;14(8):726-33
references.pmid: 9789098
references.citation: J Mol Biol. 1986 Jul 20;190(2):159-65
references.pmid: 3641921