FAMSA: Fast and accurate multiple sequence alignment of huge protein families

Abstract

Rapid development of modern sequencing platforms has contributed to the unprecedented growth of protein families databases. The abundance of sets containing hundreds of thousands of sequences is a formidable challenge for multiple sequence alignment algorithms. The article introduces FAMSA, a new progressive algorithm designed for fast and accurate alignment of thousands of protein sequences. Its features include the utilization of the longest common subsequence measure for determining pairwise similarities, a novel method of evaluating gap costs, and a new iterative refinement scheme. What matters is that its implementation is highly optimized and parallelized to make the most of modern computer platforms. Thanks to the above, quality indicators, i.e. sum-of-pairs and total-column scores, show FAMSA to be superior to competing algorithms, such as Clustal Omega or MAFFT for datasets exceeding a few thousand sequences. Quality does not compromise on time or memory requirements, which are an order of magnitude lower than those in the existing solutions. For example, a family of 415519 sequences was analyzed in less than two hours and required no more than 8 GB of RAM. FAMSA is available for free at http://sun.aei.polsl.pl/REFRESH/famsa .

Full text

Its licence does not allow us to show the full text. Read it at PubMed Central:

References 45

1. 1.

   Chatzou M.. Multiple sequence alignment modeling: methods and applications. Brief. Bioinform. (2015 ).

   Not in our library10.1093/bib/bbv099

2. 2.

   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 Res. 22(22), 4673–4680 (1994 ).

   Not in our library10.1093/nar/22.22.4673

3. 3.

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

   Not in our library10.1101/gr.2821705

4. 4.
   MUSCLE: a multiple sequence alignment method with reduced time and space complexity · 2004

   No notice
5. 5.

   Notredame C., Higgins D. G. & Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302(1), 205–217 (2000 ).

   Not in our library10.1006/jmbi.2000.4042

6. 6.
   Kalign – an accurate and fast multiple sequence alignment algorithm · 2005

   No notice
7. 7.

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

   Not in our library10.1093/nar/gkn1006

8. 8.

   Wu S. & Manber U. Fast text searching: allowing errors. Commun. ACM 35(10), 83–91 (1992 ).

   Not in our library

9. 9.

   Muth R. & Manber U. Approximate multiple string search in Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, 75–86 (1996).

   Not in our library

10. 10.

    Deorowicz S., Debudaj-Grabysz A. & Gudyś A. Kalign-LCS—A More Accurate and Faster Variant of Kalign2 Algorithm for the Multiple Sequence Alignment Problem in Man-Machine Interactions 3, AISC 242 (eds Gruca A..) 495–502 (Springer-Verlag, 2014 ).

    Not in our library

11. 11.

    Katoh K. & Toh H. PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences. Bioinformatics 23, 372–374 (2007 ).

    Not in our library10.1093/bioinformatics/btl592

12. 12.

    Katoh K. & Toh H. Recent developments in the MAFFT multiple sequence alignment program. Brief. Bioinform. 9(4), 286–298 (2008 ).

    Not in our library10.1093/bib/bbn013

13. 13.

    Sievers F.. Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Mol. Syst. Biol. 7, 539 (2011 ).

    Not in our library10.1038/msb.2011.75

14. 14.

    Blackshields G., Sievers F., Shi W., Wilm A. & Higgins D. G. Sequence embedding for fast construction of guide trees for multiple sequence alignment. Algorithm. Mol. Biol. 5(1), 21 (2010 ).

    Not in our library10.1186/1748-7188-5-21

15. 15.

    Nguyen Np. D., Mirarab S., Kumar K. & Warnow T. Ultra-large alignments using phylogeny-aware profiles. Genome Biol. 16, 124 (2015 ).

    Not in our library10.1186/s13059-015-0688-z

16. 16.

    Intel Corporation, Intel 64 and IA-32 Architectures Software Developer’s Manual. Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B, 3C and 3D http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html. (Accessed: 30th June 2016).

    Not in our library

17. 17.

    Sibson R. SLINK: An optimally efficient algorithm for the single-link cluster method. Comput. J. 16, 30–34 (1973 ).

    Not in our library

18. 18.

    Yamada K. & Tomii K. Revisiting amino acid substitution matrices for identifying distantly related proteins. Bioinformatics 30, 317–325 (2014 ).

    Not in our library10.1093/bioinformatics/btt694

19. 19.

    Gudyś A. & Deorowicz S. QuickProbs 2: towards rapid construction of high-quality alignments of large protein families. Preprint available at: http://arxiv.org/abs/1512.07437 (2015 ).

    Not in our library10.1038/srep41553

20. 20.

    Mizuguchi K., Deane C. M., Blundell T. L. & Overington J. P. HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci. 7(11), 2469–2471 (1998 ).

    Not in our library10.1002/pro.5560071126

21. 21.

    Punta M.. The Pfam protein families database. Nucleic Acids Res. 40(D1), D281–D288 (2012 ).

    Not in our library10.1093/nar/gkm960

22. 22.

    Plyusnin I. & Holm L. Comprehensive comparison of graph based multiple protein sequence alignment strategies. BMC Bioinformatics 13, 64 (2012 ).

    Not in our library10.1186/1471-2105-13-64

23. 23.

    Gusfield D. Algorithms on Strings, Trees and Sequences (Cambridge University Press, 1997 ).

    Not in our library

24. 24.

    Hyyrö H. Bit-parallel LCS-length computation revisited in Proceedings of the 15th Australian Workshop on Combinatorial Algorithms, 16–27 (2004).

    Not in our library

25. 25.

    Khronos Group, The open standard for parallel programming of heterogeneous systems. https://www.khronos.org/opencl. (Accessed: 30th June 2016).

    Not in our library

26. 26.

    Saitou N. & Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4(4), 406–425 (1987 ).

    Not in our library10.1093/oxfordjournals.molbev.a040454

27. 27.

    Sokal R. R. & Michener C. D. A statistical method for evaluating systematic relationships. Univ. Kans. Sci. Bull. 38, 1409–1438 (1958 ).

    Not in our library

28. 28.

    Florek K., Łukaszewicz J., Perkal J., Steinhaus H. & Zubrzycki S. Sur la liaison et la division des points d’un ensemble fini. Colloq Math 2, 282–285 (1951 ).

    Not in our library

29. 29.

    Wheeler T. J. & Kececioglu J. D. Multiple alignment by aligning alignments. Bioinformatics 23(13), i559–i568 (2007 ).

    Not in our library10.1093/bioinformatics/btm226

30. 30.
    Optimizing substitution matrix choice and gap parameters for sequence alignment · 2009

    Not checked
31. 31.

    Chakrabarti S.. Refining multiple sequence alignments with conserved core regions. Nucleic Acids Res. 34(9), 2598–2606 (2006 ).

    Not in our library10.1093/nar/gkl274

32. 32.

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

    Not in our library10.1093/bioinformatics/btq338

33. 33.

    Edgar R. C. QSCORE multiple alignment scoring software. http://www.drive5.com/qscore. (Accessed: 30th June 2016).

    Not in our library

34. 34.

    Thompson J. D., Plewniak F. & Poch O. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15(1), 87–88 (1999 ).

    Not in our library10.1093/bioinformatics/15.1.87

35. 35.

    Raghava G., Searle G., Audley P., Barber J. & Barton G. OXBench: A benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics 4(1), 47 (2003 ).

    Not in our library10.1186/1471-2105-4-47

36. 36.

    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 ).

    Not in our library10.1093/bioinformatics/bth493

37. 37.

    Katoh K. & Standley D. M. MAFFT multiple sequence alignment software version 7: improvements in performance and usability. Mol. Biol. Evol. 30, 772–780 (2013 ).

    Not in our library10.1093/molbev/mst010

38. 38.

    Sievers F., Dinnen D., Wilm A. & Higgins D. G. Making automated multiple alignments of very large numbers of protein sequences. Bioinformatics 29, 989–995 (2013 ).

    Not in our library10.1093/bioinformatics/btt093

39. 39.

    Gudyś A. & Deorowicz S. QuickProbs—A Fast Multiple Sequence Alignment Algorithm Designed for Graphics Processors. PLoS One 9(7), e103051 (2014 ).

    Not in our library10.1371/journal.pone.0088901

40. 40.

    Ye Y.. GLProbs: Aligning Multiple Sequences Adaptively. IEEE/ACM Trans. Comput. Biol. Bioinf. 12, 67–78 (2015 ).

    Not in our library10.1109/tcbb.2014.2316820

Cited by papers we hold 6

• The Pfam protein families database: embracing AI/ML · 2024
  No notice
• A simple guide to de novo transcriptome assembly and annotation · 2022
  No notice
• Highly accurate protein structure prediction with AlphaFold · 2021
  No notice
• A genomic catalog of Earth’s microbiomes · 2020
  Corrected
• Functional and genetic markers of niche partitioning among enigmatic members of the human oral microbiome · 2020
  No notice
• New insights from uncultivated genomes of the global human gut microbiome · 2019
  No notice

Reads

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.