Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 205

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

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

Open access
Deorowicz, Sebastian, Debudaj-Grabysz, Agnieszka, Gudyś, Adam·2016·Scientific Reports

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/srep33964

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 1 references

Research works printed but not linked: 41

  1. Chatzou, M. et al. Multiple sequence alignment modeling: methods and applications. Brief. Bioinform. 10.1093/bib/bbv099 (2015). · DOI · Paper page
  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). · DOI · Paper page
  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). · DOI · Paper page
  4. Edgar, R. C. MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics 5, 113 (2004). · DOI · Paper page
  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). · DOI · Paper page
  6. Lassmann, T. & Sonnhammer, E. L. L. Kalign—an accurate and fast multiple sequence alignment algorithm. BMC Bioinformatics 6, 298 (2005). · DOI · Paper page
  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). · DOI · Paper page
  8. Wu, S. & Manber, U. Fast text searching: allowing errors. Commun. ACM 35(10), 83–91 (1992). · DOI · Paper page
  9. Muth, R. & Manber, U. Approximate multiple string search in Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, 75–86 (1996). · doi:10.1007/3-540-61258-0_7
  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. et al.) 495–502 (Springer-Verlag, 2014). · doi:10.1007/978-3-319-02309-0_54
  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). · DOI
  12. Katoh, K. & Toh, H. Recent developments in the MAFFT multiple sequence alignment program. Brief. Bioinform. 9(4), 286–298 (2008). · DOI · Paper page
  13. Sievers, F. et al. Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Mol. Syst. Biol. 7, 539 (2011). · DOI · Paper page
  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). · DOI
  15. Nguyen, Np. D., Mirarab, S., Kumar, K. & Warnow, T. Ultra-large alignments using phylogeny-aware profiles. Genome Biol. 16, 124 (2015). · DOI
  16. Sibson, R. SLINK: An optimally efficient algorithm for the single-link cluster method. Comput. J. 16, 30–34 (1973). · DOI · Paper page
  17. Yamada, K. & Tomii, K. Revisiting amino acid substitution matrices for identifying distantly related proteins. Bioinformatics 30, 317–325 (2014). · DOI
  18. 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). · arXiv
  19. 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). · DOI · Paper page
  20. Punta, M. et al. The Pfam protein families database. Nucleic Acids Res. 40(D1), D281–D288 (2012). · DOI · Paper page
  21. Plyusnin, I. & Holm, L. Comprehensive comparison of graph based multiple protein sequence alignment strategies. BMC Bioinformatics 13, 64 (2012). · doi:10.1186/1471-2105-13-64
  22. Gusfield, D. Algorithms on Strings, Trees and Sequences (Cambridge University Press, 1997). · DOI · Paper page
  23. Hyyrö, H. Bit-parallel LCS-length computation revisited in Proceedings of the 15th Australian Workshop on Combinatorial Algorithms, 16–27 (2004).
  24. Saitou, N. & Nei, M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4(4), 406–425 (1987).
  25. Sokal, R. R. & Michener, C. D. A statistical method for evaluating systematic relationships. Univ. Kans. Sci. Bull. 38, 1409–1438 (1958).
  26. 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). · DOI · Paper page
  27. Wheeler, T. J. & Kececioglu, J. D. Multiple alignment by aligning alignments. Bioinformatics 23(13), i559–i568 (2007). · DOI · Paper page
  28. Edgar, R. C. Optimizing substitution matrix choice and gap parameters for sequence alignment BMC Bioinformatics 10, 396 (2009). · DOI
  29. Chakrabarti, S. et al. Refining multiple sequence alignments with conserved core regions. Nucleic Acids Res. 34(9), 2598–2606 (2006). · DOI
  30. 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). · DOI · Paper page
  31. 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). · DOI · Paper page
  32. 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). · DOI · Paper page
  33. 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). · DOI · Paper page
  34. 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). · DOI
  35. Gudyś, A. & Deorowicz, S. QuickProbs—A Fast Multiple Sequence Alignment Algorithm Designed for Graphics Processors. PLoS One 9(7), e103051 (2014). · doi:10.1371/journal.pone.0088901
  36. Ye, Y. et al. GLProbs: Aligning Multiple Sequences Adaptively. IEEE/ACM Trans. Comput. Biol. Bioinf. 12, 67–78 (2015). · DOI
  37. Boyce, K., Sievers, F. & Higgins, D. G. Simple chained guide trees give high-quality protein multiple sequence alignments. Proc. Nat. Acad. Sci. USA 111(29), 10556–10561 (2014). · DOI
  38. Boyce, K., Sievers, F. & Higgins, D. G. Reply to Tan et al.: Differences between real and simulated proteins in multiple sequence alignments. Proc. Nat. Acad. Sci. USA 112(2), E101 (2015). · doi:10.1073/pnas.1419351112
  39. Tan, G., Gil, M., Löytynoja, A. P., Goldman, N. & Dessimoz, C. Simple chained guide trees give poorer multiple sequence alignments than inferred trees in simulation and phylogenetic benchmarks. Proc. Nat. Acad. Sci. USA 112, E99–E100 (2015). · DOI
  40. Sackin, M. J. “Good” and “bad” phenograms. Syst. Biol. 21(2), 225–226 (1972). · doi:10.1093/sysbio/21.2.225
  41. Fox, G., Sievers, F. & Higgins, D. G. Using de novo protein structure predictions to measure the quality of very large multiple sequence alignments. Bioinformatics 32(6), 814–820 (2016). · DOI

Cited by

See all 205

Metadata

Authors
Deorowicz, S., Debudaj-Grabysz, A., & Gudyś, A.
Venue
Scientific Reports
Published
2016-09-27
Volume
6
Issue
1
Pages
33964-33964
ISSN
2045-2322 (ISSN-L)
OpenAlex
W3101667854
Cited by
205
References
1
FWCI
2.26
Type
journal article
Language
en
Open access
gold
Licence

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: FAMSA: Fast and accurate multiple sequence alignment of huge protein families. https://app.cochat.ai/papers/10.1038/srep33964
The paper
Deorowicz, S., Debudaj-Grabysz, A., & Gudyś, A. (2016). FAMSA: Fast and accurate multiple sequence alignment of huge protein families. Scientific Reports. https://doi.org/10.1038/srep33964

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.