[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Kalign-LCS — A More Accurate and Faster Variant of Kalign2 Algorithm for the Multiple Sequence Alignment Problem

  • Conference paper
Man-Machine Interactions 3

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 242))

  • 1827 Accesses

Abstract

Determination of similarities between species is a crucial issue in life sciences. This task is usually done by comparing fragments of genomic or proteomic sequences of organisms subjected to analysis. The basic procedure which facilitates these comparisons is called multiple sequence alignment. There are a lot of algorithms aiming at this problem, which are either accurate or fast. We present Kalign-LCS, a variant of fast Kalign2 algorithm, that addresses the accuracy vs. speed trade-off. It employs the longest common subsequence measure and was thoroughly optimized. Experiments show that it is faster than Kalign2 and produces noticeably more accurate alignments.

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

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 143.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 179.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Aluru, S. (ed.): Handbook of Computational Molecular Biology, 1st edn. Chapman & Hall/CRC (2006)

    Google Scholar 

  2. Carrillo, H., Lipman, D.J.: The multiple sequence alignment problem in biology. SIAM Journal of Applied Mathematics 48(5), 1073–1082 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  3. Deorowicz, S.: Serial and parallel subsequence finding algorithms. Studia Informatica 31(4B(93)) (2011)

    Google Scholar 

  4. Do, C.B., Katoh, K.: Protein Multiple Sequence Alignment. In: Methods in Molecular Biology, ch. 25, vol. 484. Humana Press (2008)

    Google Scholar 

  5. Do, C.B., Mahabhashyam, M.S.P., Brudno, M., Batzoglou, S.: ProbCons: Probabilistic consistency-based multiple sequence alignment. Genome Research 15(2), 330–340 (2005)

    Article  Google Scholar 

  6. Edgar, R.C.: Quality measures for protein alignment benchmarks. Nucleic Acids Research 38(7), 2145–2153 (2010)

    Article  Google Scholar 

  7. Hyyrö, H.: Bit-parallel LCS-length computation revisited. In: Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms (AWOCA 2004), pp. 16–27 (2004)

    Google Scholar 

  8. Katoh, K., Misawa, K., Kuma, K., Miyata, T.: MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Research 30(14), 3059–3066 (2002)

    Article  Google Scholar 

  9. Lassmann, T., Frings, O., Sonnhammer, E.L.L.: Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features. Nucleic Acids Research 37(3), 858–865 (2009)

    Article  Google Scholar 

  10. Lassmann, T., Sonnhammer, E.L.L.: Kalign — an accurate and fast multiple sequence alignment algorithm. BMC Bioinformatics 6, 298 (2005)

    Article  Google Scholar 

  11. Liu, Y., Schmidt, B., Maskell, D.L.: MSAProbs: multiple sequence alignment based on pair hidden Markov models and partition function posterior probabilities. Bioinformatics 26(16), 1958–1964 (2010)

    Article  Google Scholar 

  12. Muth, R., Manber, U.: Approximate multiple string search. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol. 1075, pp. 75–86. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  13. Myers, E.W., Miller, W.: Optimal alignments in linear space. Computer Applications in the Biosciences 4(1), 11–17 (1988)

    Google Scholar 

  14. Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: A novel method for fast and accurate multiple sequence alignment. Journal of Molecular Biology 302(1), 205–217 (2000)

    Article  Google Scholar 

  15. Sievers, F., Wilm, A., Dineen, D., Gibson, T.J., Karplus, K., Li, W., Lopez, R., McWilliam, H., Remmert, M., Söding, J., Thompson, J.D., Higgins, D.G.: Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Molecular Systems Biology 7(539), 1–6 (2011)

    Google Scholar 

  16. Thompson, J.D., Higgins, D.G., Gibson, T.J.: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research 22(22), 4673–4680 (1994)

    Article  Google Scholar 

  17. Thompson, J.D., Koehl, P., Ripp, R., Poch, O.: BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. Proteins 61(1), 127–136 (2005)

    Article  Google Scholar 

  18. Van Walle, I., Lasters, I., Wyns, L.: SABmark–a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics 21(7), 1267–1268 (2005)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sebastian Deorowicz .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Deorowicz, S., Debudaj-Grabysz, A., Gudyś, A. (2014). Kalign-LCS — A More Accurate and Faster Variant of Kalign2 Algorithm for the Multiple Sequence Alignment Problem. In: Gruca, D., Czachórski, T., Kozielski, S. (eds) Man-Machine Interactions 3. Advances in Intelligent Systems and Computing, vol 242. Springer, Cham. https://doi.org/10.1007/978-3-319-02309-0_54

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-02309-0_54

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-02308-3

  • Online ISBN: 978-3-319-02309-0

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics