Abstract
The local sequence alignment problem is the detection of similar subsequences in two given sequences of lengths n ≥m. Unfortunately the common notion of local alignment suffers from some wellknown anomalies which result from not taking into account the lengths of the aligned subsequences. We introduce the length restricted local alignment problem which includes as a constraint an upper limit T on the length of one of the subsequences to be aligned.We propose an efficient approximation algorithm, which finds a solution satisfying the length bound, and whose score is within difference Δ of the optimum score for any given positive integer Δ. The algorithm runs in time O (nmT/Δ) using O (mT/Δ) space. We also introduce the cyclic local alignment problem and show how our idea can be applied to this case as well. This is a dual approach to the well-known cyclic edit distance problem.
Supported in part by NSF Grant No.CCR.9821038.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N.N. Alexandrov and V.V. Solovyev. Statistical significance of ungapped alignments. Pacific Symposium on Biocomputing (PSB-98), (eds. R. Altman, A. Dunker, L. Hunter, T. Klein), pages 463–472, 1998.
S.F. Altschul, T.L. Madden, A.A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D.J. Lipman. Gapped Blast and Psi-Blast:a new generation of protein database search programs. Nucleic Acids Research 25:3389–3402,1997.
A.N. Arslan, Ö. Eğecioğlu, and P.A. Pevzner. A new approach to sequence comparison:Normalized local alignment. Bioinformatics 17(4):327–337, 2001.
H. Bunke and U. Bühler. Applications of approximate string matching to 2d shape recognition. Pattern Recognition 26(12):1797–1812, 1993.
K-L. Chung. An improved algorithm for solving the banded cyclic string-to-string correction problem. Theoretical Computer Science 201:275–279, 1998.
K.S. Fu and S.Y. Lu. Size normalization and pattern orientation problems in syntactics clustering. IEEE Trans. Systems Man Cybernet 9:55–58, 1979.
J.W. Gorman, O.R. Mitchell, and F.P. Kuhl. Partial shape recognition using dynamic programming. IEEE Trans. Pattern Anal. Mech. Intell. PAMI-10 pages 257–266, 1988.
J. Gregor and M.G. Thomason. Efficient dynamic programming alignment of cyclic shifts by shift elimination. Pattern Recognition 29(7):1179–1185, 1996.
G.M. Landau, E.W. Myers, and J.P. Schmidt. Incremental string comparison. Siam J. Comput., 27(2):557–582, 1998.
M. Maes.On a cyclic string-to-string correction problem. Information Processing Letters 35:73–78, 1990.
T.F. Smith and M.S. Waterman.The identification of common molecular subsequences, J. of Molecular Biology 147:195–197, 1981.
S. Uliel, A. Fliess, A. Amir, and R. Unger. A simple algorithm for detecting circular permutations in proteins. Bioinformatics 15(11):930–936, 1999.
M.S. Waterman. Introduction to computational biology. Chapman & Hall, 1995.
Z. Zhang, P. Berman, and W. Miller. Alignments without low-scoring regions. J. Comput. Biol., 5:197–200, 1998.
Z. Zhang, P. Berman, T. Wiehe, and W. Miller. Post-processing long pairwise alignments. Bioinformatics 15:1012–1019, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arslan, A.N., Eğecioğlu, Ö. (2002). Algorithms for Local Alignment with Length Constraints* . In: Rajsbaum, S. (eds) LATIN 2002: Theoretical Informatics. LATIN 2002. Lecture Notes in Computer Science, vol 2286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45995-2_9
Download citation
DOI: https://doi.org/10.1007/3-540-45995-2_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43400-9
Online ISBN: 978-3-540-45995-8
eBook Packages: Springer Book Archive