FAMSA: Fast and accurate multiple sequence alignment of huge protein families.
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.
Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland.
Sebastian
S
Deorowicz
Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland.
Agnieszka
A
Debudaj-Grabysz
Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland.
Adam
A
Gudyś
Bioinformatics. 2010 Aug 15;26(16):1958-64
20576627
Mol Syst Biol. 2011 Oct 11;7:539
21988835
Mol Biol Evol. 2013 Apr;30(4):772-80
23329690
Nucleic Acids Res. 2006 May 17;34(9):2598-606
16707662
Mol Biol Evol. 1987 Jul;4(4):406-25
3447015
Bioinformatics. 2013 Apr 15;29(8):989-95
23428640
Bioinformatics. 1999 Jan;15(1):87-8
10068696
Nucleic Acids Res. 2008 Jan;36(Database issue):D281-8
18039703
BMC Bioinformatics. 2009 Dec 02;10:396
19954534
BMC Bioinformatics. 2003 Oct 10;4:47
14552658
PLoS One. 2014 Feb 25;9(2):e88901
24586435
Nucleic Acids Res. 2009 Feb;37(3):858-65
19103665
Proc Natl Acad Sci U S A. 2014 Jul 22;111(29):10556-61
25002495
Bioinformatics. 2005 Apr 1;21(7):1267-8
15333456
Sci Rep. 2017 Jan 31;7:41553
28139687
Proc Natl Acad Sci U S A. 2015 Jan 13;112(2):E101
25564671
Genome Biol. 2015 Jun 16;16:124
26076734
IEEE/ACM Trans Comput Biol Bioinform. 2015 Jan-Feb;12(1):67-78
26357079
BMC Bioinformatics. 2005 Dec 12;6:298
16343337
J Mol Biol. 2000 Sep 8;302(1):205-17
10964570
Algorithms Mol Biol. 2010 May 14;5:21
20470396
Genome Res. 2005 Feb;15(2):330-40
15687296
Bioinformatics. 2007 Jul 1;23(13):i559-68
17646343
Proc Natl Acad Sci U S A. 2015 Jan 13;112(2):E99-100
25564672
Bioinformatics. 2014 Feb 01;30(3):317-25
24281694
Protein Sci. 1998 Nov;7(11):2469-71
9828015
BMC Bioinformatics. 2004 Aug 19;5:113
15318951
BMC Bioinformatics. 2012 Apr 29;13:64
22540977
Bioinformatics. 2016 Mar 15;32(6):814-20
26568625
Bioinformatics. 2007 Feb 1;23(3):372-4
17118958
Brief Bioinform. 2016 Nov;17(6):1009-1023
26615024
Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
7984417
Brief Bioinform. 2008 Jul;9(4):286-98
18372315