MUSCLE: a multiple sequence alignment method with reduced time and space complexity Export

@article{citeulike:692, abstract = {BACKGROUND:In a previous paper, we introduced MUSCLE, a new program for creating multiple alignments of protein sequences, giving a brief summary of the algorithm and showing MUSCLE to achieve the highest scores reported to date on four alignment accuracy benchmarks. Here we present a more complete discussion of the algorithm, describing several previously unpublished techniques that improve biological accuracy and / or computational complexity. We introduce a new option, MUSCLE-fast, designed for high-throughput applications. We also describe a new protocol for evaluating objective functions that align two profiles.RESULTS:We compare the speed and accuracy of MUSCLE with CLUSTALW, Progressive POA and the MAFFT script FFTNS1, the fastest previously published program known to the author. Accuracy is measured using four benchmarks: BAliBASE, PREFAB, SABmark and SMART. We test three variants that offer highest accuracy (MUSCLE with default settings), highest speed (MUSCLE-fast), and a carefully chosen compromise between the two (MUSCLE-prog). We find MUSCLE-fast to be the fastest algorithm on all test sets, achieving average alignment accuracy similar to CLUSTALW in times that are typically two to three orders of magnitude less. MUSCLE-fast is able to align 1,000 sequences of average length 282 in 21 seconds on a current desktop computer.CONCLUSIONS:MUSCLE offers a range of options that provide improved speed and / or alignment accuracy compared with currently available programs. MUSCLE is freely available at http://www.drive5.com/muscle.}, address = {Department of Plant and Microbial Biology, 461 Koshland Hall, University of California, Berkeley, CA 94720-3102, USA. bob@drive5.com}, author = {Edgar, Robert}, citeulike-article-id = {692}, citeulike-linkout-0 = {http://dx.doi.org/10.1186/1471-2105-5-113}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/15318951}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=15318951}, day = {19}, doi = {10.1186/1471-2105-5-113}, issn = {1471-2105}, journal = {BMC Bioinformatics}, keywords = {compare, comps, evolution, major-proposal, sequence}, month = {August}, number = {1}, pages = {113+}, posted-at = {2006-11-13 20:28:08}, priority = {5}, title = {MUSCLE: a multiple sequence alignment method with reduced time and space complexity}, url = {http://dx.doi.org/10.1186/1471-2105-5-113}, volume = {5}, year = {2004} }

TY - JOUR ID - citeulike:692 L3 - citeulike-article-id:692 N2 - BACKGROUND:In a previous paper, we introduced MUSCLE, a new program for creating multiple alignments of protein sequences, giving a brief summary of the algorithm and showing MUSCLE to achieve the highest scores reported to date on four alignment accuracy benchmarks. Here we present a more complete discussion of the algorithm, describing several previously unpublished techniques that improve biological accuracy and / or computational complexity. We introduce a new option, MUSCLE-fast, designed for high-throughput applications. We also describe a new protocol for evaluating objective functions that align two profiles.RESULTS:We compare the speed and accuracy of MUSCLE with CLUSTALW, Progressive POA and the MAFFT script FFTNS1, the fastest previously published program known to the author. Accuracy is measured using four benchmarks: BAliBASE, PREFAB, SABmark and SMART. We test three variants that offer highest accuracy (MUSCLE with default settings), highest speed (MUSCLE-fast), and a carefully chosen compromise between the two (MUSCLE-prog). We find MUSCLE-fast to be the fastest algorithm on all test sets, achieving average alignment accuracy similar to CLUSTALW in times that are typically two to three orders of magnitude less. MUSCLE-fast is able to align 1,000 sequences of average length 282 in 21 seconds on a current desktop computer.CONCLUSIONS:MUSCLE offers a range of options that provide improved speed and / or alignment accuracy compared with currently available programs. MUSCLE is freely available at http://www.drive5.com/muscle. IS - 1 JF - BMC Bioinformatics SN - 1471-2105 AD - Department of Plant and Microbial Biology, 461 Koshland Hall, University of California, Berkeley, CA 94720-3102, USA. bob@drive5.com TI - MUSCLE: a multiple sequence alignment method with reduced time and space complexity VL - 5 SP - 113 KW - compare KW - comps KW - evolution KW - major-proposal KW - sequence AU - Edgar, Robert PY - 2004/08/19/ UR - http://dx.doi.org/10.1186/1471-2105-5-113 ER -