General continuous-time Markov model of sequence evolution via insertions/deletions: local alignment probability computation.
BACKGROUND
Insertions and deletions (indels) account for more nucleotide differences between two related DNA sequences than substitutions do, and thus it is imperative to develop a method to reliably calculate the occurrence probabilities of sequence alignments via evolutionary processes on an entire sequence. Previously, we presented a perturbative formulation that facilitates the ab initio calculation of alignment probabilities under a continuous-time Markov model, which describes the stochastic evolution of an entire sequence via indels with quite general rate parameters. And we demonstrated that, under some conditions, the ab initio probability of an alignment can be factorized into the product of an overall factor and contributions from regions (or local alignments) delimited by gapless columns.


RESULTS
Here, using our formulation, we attempt to approximately calculate the probabilities of local alignments under space-homogeneous cases. First, for each of all types of local pairwise alignments (PWAs) and some typical types of local multiple sequence alignments (MSAs), we numerically computed the total contribution from all parsimonious indel histories and that from all next-parsimonious histories, and compared them. Second, for some common types of local PWAs, we derived two integral equation systems that can be numerically solved to give practically exact solutions. We compared the total parsimonious contribution with the practically exact solution for each such local PWA. Third, we developed an algorithm that calculates the first-approximate MSA probability by multiplying total parsimonious contributions from all local MSAs. Then we compared the first-approximate probability of each local MSA with its absolute frequency in the MSAs created via a genuine sequence evolution simulator, Dawg. In all these analyses, the total parsimonious contributions approximated the multiplication factors fairly well, as long as gap sizes and branch lengths are at most moderate. Examination of the accuracy of another indel probabilistic model in the light of our formulation indicated some modifications necessary for the model's accuracy improvement.


CONCLUSIONS
At least under moderate conditions, the approximate methods can quite accurately calculate ab initio alignment probabilities under biologically more realistic models than before. Thus, our formulation will provide other indel probabilistic models with a sound reference point.
Department of Bioscience and Bioinformatics, Kyushu Institute of Technology, Iizuka, 820-8502, Japan. kezawa.ezawa3@gmail.com.|Department of Biology and Biochemistry, University of Houston, Houston, TX, 77204-5001, USA. kezawa.ezawa3@gmail.com.
Kiyoshi
http://orcid.org/0000-0003-4906-8578
K
Ezawa
Evolutionary simulation; Indel likelihood; Insertion/deletion (indel); Perturbation theory; Power-law length distribution; Practically exact solution; Sequence alignment probability; Stochastic evolutionary model
PLoS Comput Biol. 2007 Aug;3(8):e123
17784778
BMC Bioinformatics. 2015 Dec 10;16:406
26652060
PLoS One. 2012;7(4):e34572
22536326
Bioinformatics. 2001 Sep;17(9):803-20
11590097
Mol Biol Evol. 2009 Feb;26(2):473-80
19042944
J Mol Biol. 2003 Oct 17;333(2):453-60
14529629
Bull Math Biol. 2013 Dec;75(12):2529-50
24135792
Nature. 2004 May 27;429(6990):382-8
15164055
Curr Genomics. 2007 Sep;8(6):370-8
19412437
Bioinformatics. 2007 Feb 1;23(3):289-97
17110370
Curr Opin Plant Biol. 2007 Apr;10(2):149-55
17300983
Proc Natl Acad Sci U S A. 2003 Apr 15;100(8):4661-5
12672966
PLoS Comput Biol. 2008 Sep 19;4(9):e1000172
18787703
BMC Bioinformatics. 2015 Apr 01;16:108
25888064
Bioinformatics. 2003;19 Suppl 1:i147-57
12855451
Genome Res. 2008 Feb;18(2):298-309
18073381
Bioinformatics. 2008 Oct 15;24(20):2403-4
18753153
J Bioinform Comput Biol. 2006 Jun;4(3):721-44
16960972
Mol Biol Evol. 2013 Mar;30(3):642-53
23144040
Mol Biol Evol. 2009 Nov;26(11):2581-93
19651852
Bioinformatics. 2006 Aug 15;22(16):2047-8
16679334
J Mol Evol. 1991 Aug;33(2):114-24
1920447
Mol Biol Evol. 2009 Aug;26(8):1879-88
19423664
Nature. 2005 Sep 1;437(7055):69-87
16136131
J Comput Biol. 2007 May;14(4):446-61
17572023
BMC Bioinformatics. 2016 Aug 11;17:304
27638547
Genome Res. 2008 Nov;18(11):1829-43
18849525
Bioinformatics. 2003 Mar 1;19(4):490-9
12611804
Proc Natl Acad Sci U S A. 2002 Oct 15;99(21):13633-5
12368483
Stat Methods Med Res. 2009 Oct;18(5):453-85
19221170
Proc Natl Acad Sci U S A. 2003 Sep 30;100(20):11484-9
14500911
BMC Bioinformatics. 2005 Mar 21;6:63
15780137
J Mol Biol. 1986 Jul 20;190(2):159-65
3641921
Mol Biol Evol. 2004 Mar;21(3):529-40
14694074
Genome Res. 2010 Jan;20(1):110-21
19858363
Gene. 2009 Jul 15;441(1-2):141-7
18614299
Bioinformatics. 2007 Dec 1;23(23):3258-62
17804440
BMC Bioinformatics. 2016 Mar 18;17 :133
26992851
Bioinformatics. 2005 Nov 1;21 Suppl 3:iii31-8
16306390
BMC Bioinformatics. 2005 Apr 01;6:83
15804354
Bioinformatics. 2007 Jul 1;23(13):i289-96
17646308
Science. 2008 Jun 20;320(5883):1632-5
18566285
J Mol Evol. 1981;17(6):368-76
7288891
Genome Biol Evol. 2015 Jan 09;7(2):567-80
25577199
Syst Biol. 2005 Jun;54(3):401-18
16012107