Algorithms for Computing Variants of the Longest Common Subsequence Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algorithms for Computing Variants of the Longest Common Subsequence Problem

Extended Abstract

  • Conference paper
Algorithms and Computation (ISAAC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4288))

Included in the following conference series:

  • 1200 Accesses

Abstract

The longest common subsequence(LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we define new variants, introducing the notion of gap-constraints in LCS problem and present efficient algorithms to solve them.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. ED’NIMBUS, http://igm.univ-mlv.fr/~peterlon/officiel/ednimbus/

  2. Altschul, S.F., Gish, W., Miller, W., Meyers, E.W., Lipman, D.J.: Basic local alignment search tool. Journal of Molecular Biology 215(3), 403–410 (1990)

    Google Scholar 

  3. Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  4. Gabow, H., Bentley, J., Tarjan, R.: Scaling and related techniques for geometry problems. In: Symposium on the Theory of Computing (STOC), pp. 135–143 (1984)

    Google Scholar 

  5. Lee, I., Apostolico, A., Iliopoulos, C.S., Park, K.: Finding approximate occurrence of a pattern that contains gaps. In: Australasian Workshop on Combinatorial Algorithms (AWOCA), pp. 89–100 (2003)

    Google Scholar 

  6. Ma, B., Zhang, K.: On the longest common rigid subsequence problem. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 11–20. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Pearson, W., Lipman, D.: Improved tools for biological sequence comparison. Proceedings of National Academy of Science, USA 85, 2444–2448 (1988)

    Article  Google Scholar 

  8. Peterlongo, P.: Private communication

    Google Scholar 

  9. Peterlongo, P., Pisanti, N., Boyer, F., Sagot, M.-F.: Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array. In: SPIRE, pp. 179–190 (2005)

    Google Scholar 

  10. van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters 6, 80–82 (1977)

    Article  MATH  Google Scholar 

  11. Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168–173 (1974)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Algorithm Design Group, Department of Computer Science, King’s College London, Strand, London, WC2R 2LS, England

    M. Sohel Rahman & Costas S. Iliopoulos

Authors
  1. M. Sohel Rahman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Costas S. Iliopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Japan Advanced Institute of Science and Technology, Japan

    Tetsuo Asano

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Rahman, M.S., Iliopoulos, C.S. (2006). Algorithms for Computing Variants of the Longest Common Subsequence Problem. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_41

Download citation

  • DOI: https://doi.org/10.1007/11940128_41

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49694-6

  • Online ISBN: 978-3-540-49696-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation