Abstract
Pairwise alignment of two sequences a, b usually assumes a and b being sequences over the same alphabet A and a scoring function s: A×A→ℝ operating on symbol pairs. The framework presented here extends this to a scoring function s: A p×B q→ℝ operating on p-tuples and q-tuples of symbols, where the scoring tuples can have an arbitrary (but not complete) overlap.
We show that, if the alphabets A and B are finite and p and q are constant, the resulting algorithms have the same asymptotic time and space complexity as their single symbol counterparts.
This framework has been applied successfully to the codon-wise alignment of prokaryotic and eukaryotic genes.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Mark A. Cohen, Steven A. Benner, and Gaston H. Gonnet. Analysis of mutation during divergent evolution: The 400 by 400 dipeptide mutation matrix. Biochem. Biophys. Res. Commun., 199:489–496, 1994.
Gaston H. Gonnet. A tutorial introduction to computational biochemistry using Darwin. E.T.H. Zurich, Switzerland, 1994.
O. Gotoh. An improved algorithm for matching biological sequences. Journal of Molecular Biology, 162:705–708, 1982.
Xiaoqiu Huang. A context dependent method for comparing sequences. In M. Crochemore and D. Gusfield, editors, Combinatorial Pattern Matching, volume 807 of Lecture Notes in Computer Science, pages 54–63. Springer-Verlag, 1994.
E. W. Myers and M. Miller. Optimal alignments in linear space. Comput. Applic. Biosci., 4:11–17, 1988.
Hannu Peltola, Hans Söderlund, and Esko Ukkonen. Algorithms for the search of amino acid patterns in nucleic acid sequences. Nucleic Acids Research, 14:99–107, 1986.
T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195–197, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knecht, L. (1995). Pairwise alignment with scoring on tuples. In: Galil, Z., Ukkonen, E. (eds) Combinatorial Pattern Matching. CPM 1995. Lecture Notes in Computer Science, vol 937. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60044-2_45
Download citation
DOI: https://doi.org/10.1007/3-540-60044-2_45
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60044-2
Online ISBN: 978-3-540-49412-6
eBook Packages: Springer Book Archive