Parametric and ensemble sequence alignment algorithms. (English) Zbl 0816.92012
Summary: Recently algorithms for parametric alignment [M. S. Waterman et al., Natl. Acad. Sci. USA 89, 6090-6093 (1992); D. Gusfield et al., Proc. Third Ann. ACM-SIAM Symp. Discrete Algorithms, 432-439 (1992)] find optimal scores for all penalty parameters, both for global and local sequence alignment. This paper reviews those techniques. Then in the main part of this paper dynamic programming methods are used to compute ensemble alignment, finding all alignment scores for all parameters. Both global and local ensemble alignments are studied, and parametric alignment is used to compute near optimal ensemble alignments.
MSC:
| 92D20 | Protein sequences, DNA sequences |
| 90C90 | Applications of mathematical programming |
| 92C40 | Biochemistry, molecular biology |
| 90C39 | Dynamic programming |
Keywords:
DNA sequencing; algorithms; parametric alignment; global and local sequence alignment; global and local ensemble alignments; near optimal ensemble alignmentsReferences:
| [1] | Byers, T. H. and M. S. Waterman. 1984. Determining all optimal and near-optimal solutions when solving shortest path porblems by dynamic programming.Oper. Res. 32, 1381. · Zbl 0553.90101 · doi:10.1287/opre.32.6.1381 |
| [2] | Fernandez-Baca, D. and S. Srinivasan. 1991. Constructing the minimization diagram of a two-parameter problem.Oper. Res. Lett. 10, 87–93. · Zbl 0717.90062 · doi:10.1016/0167-6377(91)90092-4 |
| [3] | Finkelstein, A. V. and M. A. Roytberg. 1993. Computation of biopolymers: a general approach to different problems.BioSystems 30, 1–19. · doi:10.1016/0303-2647(93)90058-K |
| [4] | Gusfield, D., K. Balasubramian and D. Naor. 1992. InProceedings of the Third Annual ACM-SIAM Discrete Algorithms, 432–439. |
| [5] | Howell, J. A., T. F. Smith and M. S. Waterman. 1980. Computation of generating functions for biological molecules.SIAM J. Appl Math. 39, 119–133. · Zbl 0445.92006 · doi:10.1137/0139010 |
| [6] | McCaskill, J. S. 1990. The equilibrium partition function and base pair binding probabilities for RNA secondary structure.Biopolymers 29, 1105–1119. · doi:10.1002/bip.360290621 |
| [7] | Naor, D. and D. Brutlag. 1993. On Suboptimal alignments of biological sequences.Proc. of the Fourth International Symposium on Combinatorial Pattern Matching, Padova, Italy, June 1993. Lecture Notes in Computer Science. |
| [8] | Needleman, S. B. and C. D. Wunsch. 1970. A general method applicable to the search for similarities in the amino acid sequences of two proteins.J. mol. Biol. 48, 443–453. · doi:10.1016/0022-2836(70)90057-4 |
| [9] | Tavaré, S. 1986. Some mathematical questions in biology–DNA sequence analysis. InLectures on Mathematics in the Life Sciences,17, 29–56. The American Mathematical Society, Providence, Rhode Island. |
| [10] | Thorne, J. L., H. Kishino and J. Felsenstein. 1991. An evolutionary model for maximum likelihood alignment of DNA sequences.J. mol. Evol. 33, 114–124. · doi:10.1007/BF02193625 |
| [11] | Thorne, J. L., H. Kishino and J. Felsenstein. 1992. Inching toward reality: an improved likelihood model of sequence evolution.J. mol. Evol. 34, 3–16. · doi:10.1007/BF00163848 |
| [12] | Vingron, M. and P. Argos. 1990. Determination of reliable regions in protein sequence alignments.Prot. Engng 3, 565–569. · doi:10.1093/protein/3.7.565 |
| [13] | Vingron, M. and M. S. Waterman. 1993. Rapid and accurate estimates of statistical significance for sequence database searches.J. mol. Biol. (in press). · Zbl 0797.92021 |
| [14] | Waterman, M. S. 1983. Sequence alignment in the neighbourhood of the optimum with general applications to dynamic programming.Natl. Acad. Sci. USA 80, 3123. · Zbl 0516.90075 · doi:10.1073/pnas.80.10.3123 |
| [15] | Waterman, M. S. 1984. General methods of sequence comparison.Bull. Math. Biol. 46, 473–500. · Zbl 0548.92006 · doi:10.1007/BF02459498 |
| [16] | Waterman, M. S. 1989. Sequence alignments. In:Mathematical Methods for DNA Sequences, M. S. Waterman (Ed.). CRC Press. · Zbl 0681.92007 |
| [17] | Waterman, M. S., M. Eggert and E. Lander. 1992. Parametric sequence comparisons. InNatl. Acad. Sci. USA,89, 6090–6093. |
| [18] | Zhang, M. Q. and T. G. Marr. 1993. Alignment of molecular sequences by random path analysis. Manuscript. · Zbl 1102.92302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
