Source-linked AI summary
Aligning 415 519 proteins in less than two hours on PC
Sebastin Deorowicz, Agnieszka Debudaj-Grabysz, Adam Gudys
TL;DR
Very large protein families challenge multiple sequence alignment because conventional approaches impose substantial computational costs and can yield unsatisfactory quality. FAMSA addresses this with a progressive algorithm using LCS-based similarities, memory-efficient tree construction, optimized profile alignment, and accuracy-oriented refinement. It achieved higher alignment quality than MAFFT and Clustal Omega on large datasets while requiring substantially less time and memory, including analysis of 415 519 sequences in less than two hours using less than 8 GB of RAM.
Problem
Protein families containing hundreds of thousands of sequences challenge multiple sequence alignment algorithms, whose time, memory, or quality can be inadequate at this scale.
Method
FAMSA is a progressive alignment algorithm combining LCS-based pairwise similarities, memory-efficient single-linkage guide-tree construction, in-place profile alignment, adjusted gap penalties, and refinement.
Results
FAMSA was significantly more accurate than MAFFT and Clustal Omega for sets of a few thousand or more sequences, while achieving lower time and memory requirements; one 415 519-sequence family took less than two hours and less than 8 GB of RAM.
Takeaways & Limitations
FAMSA's scalability in alignment quality, time, and memory makes it applicable to protein families even of a million sequences, beyond the practical range of competing software.
Takeaways & Limitations
Accuracy assessment for alignments of 10 000 or more proteins is limited by reference sets containing only a small fraction of the family members.
Abstract
from arXiv · showhide
Rapid development of modern sequencing platforms enabled an unprecedented growth of protein families databases. The abundance of sets composed of hundreds of thousands sequences is a great challenge for multiple sequence alignment algorithms. In the article we introduce FAMSA, a new progressive algorithm designed for fast and accurate alignment of thousands of protein sequences. Its features include the utilisation of longest common subsequence measure for determining pairwise similarities, a novel method of gap costs evaluation, and a new iterative refinement scheme. Importantly, its implementation is highly optimised and parallelised to make the most of modern computer platforms. Thanks to the above, quality indicators, namely sum-of-pairs and total-column scores, show FAMSA to be superior to competing algorithms like Clustal Omega or MAFFT for datasets exceeding a few thousand of sequences. The quality does not compromise time and memory requirements which are an order of magnitude lower than that of existing solutions. For example, a family of 415 519 sequences was analysed in less than two hours and required only 8GB of RAM. FAMSA is freely available at http://sun.aei.polsl.pl/REFRESH/famsa.
Introduction
FAMSA is a progressive multiple sequence alignment algorithm for large protein families, designed to improve accuracy while reducing the time and memory costs that limit existing approaches. It combines LCS-based similarities, memory-efficient tree construction, optimized profile alignment, and refinement to outperform competing methods on large datasets.
- Motivation: FAMSA targets large protein families where existing algorithms can be computationally feasible but often produce unsatisfactory alignment quality.MAFFT and Clustal Omega can process families of up to 100,000 proteins, but their quality is often unsatisfactory for such problems.
- Method: FAMSA uses longest common subsequences for pairwise similarities and computes them with a multithreaded, bit-parallel algorithm suited to modern processor extensions.Unlike MAFFT and Clustal Omega, it calculates all pairwise similarities while using AVX-oriented computation.
- Method: A memory-saving single-linkage algorithm constructs the guide tree in O(k) space, while in-place profile alignment avoids memory reallocations during progressive alignment.Here, k denotes the number of input sequences.
- Accuracy: FAMSA combines LCS similarity measurement, the MIQS substitution matrix, size-adjusted gap penalties, and refinement to improve alignment accuracy.The gap-penalty adjustment is described as particularly beneficial for large sequence sets.
- Results: For sets exceeding 25 000 proteins, FAMSA aligned 35% more columns than MAFFT and 25% more than Clustal Omega.On the 415 519-sequence benchmark, it restored 4 times more columns than competitors while using less time and memory.
Methods
FAMSA uses a progressive alignment pipeline with LCS-based similarities, guide-tree construction, profile merging, and optional refinement. Its implementation combines specialized profile representations, parallel computation, and gap-cost handling to reduce time and memory demands for large protein families.
- Pipeline: FAMSA proceeds through pairwise similarity calculation, guide-tree determination, progressive profile merging, and optional iterative refinement.These are the four stages identified for the algorithm.
- Pairwise similarities: LCS length estimates pairwise similarity, normalized by indel distance to compensate for sequence-length effects and squared to penalize differences more strongly.The LCS is computed with bit-parallel dynamic programming and can be distributed across threads and vector operations.
- Guide tree: Single-linkage guide-tree construction is incremental and fast, requiring O(k) space rather than O(k^2) for methods such as UPGMA.FAMSA performs similarity calculation and tree generation simultaneously to restrict memory usage.
- Profile representation: A gapped sequence representation stores symbols, preceding-gap counts, and dynamic position statistics, enabling rapid gap insertion and memory-frugal profile alignment.The representation uses approximately 13 times the sequence length and supports moving whole sequences instead of copying symbols individually.
- Parallelization: Independent profile alignments in the lower guide-tree levels are distributed across multiple threads, while FAMSA also supports GPU-based LCS computation.The current implementation does not parallelize the dynamic programming computation within a single profile alignment.
- Gap costs: Gap handling distinguishes terminal opens, terminal extensions, internal opens, and internal extensions when inserting columns into profiles.This correction avoids overestimating gap opens when profiles already contain gaps.
Results
Across HomFam and extHomFam, FAMSA combines strong alignment quality with substantially lower runtime and memory use, especially as protein-family size grows. It is competitive on classic smaller benchmarks while leading large-family comparisons.
- Benchmark design: 380 extHomFam families span 218 to 415 519 sequences, providing a benchmark focused on large-scale alignment.The benchmark includes families enriched from Homstrad and PFam, with subsets divided by sequence count.
- Compared algorithms: FAMSA was compared with MUSCLE, Kalign 2, Kalign-LCS, Clustal Omega, and MAFFT on families containing thousands of sequences.Additional consistency-based algorithms were evaluated on smaller classic benchmarks.
- HomFam accuracy: For k ≤3000, FAMSA was inferior to both Clustal Omega configurations and comparable to MAFFT-default; for 3000 < k ≤10000, it ranked first in SP and second in TC.For the largest HomFam subgroup, FAMSA led on both measures.
- extHomFam accuracy: For 4000 < k ≤25000, FAMSA became the best aligner, while Clustal-iter2 exceeded it only by a small margin on the smallest subset.Fast MAFFT variants and MUSCLE produced inferior results in the reported extHomFam comparisons.
- extHomFam accuracy: 35% and 25% more columns were correctly aligned by FAMSA than the most accurate MAFFT and Clustal Omega variants, respectively, on extra-large families.The quality advantage increased across consecutive extHomFam subsets.
- Runtime and memory: 7 hours and 40 minutes was FAMSA's runtime for all extHomFam sets, versus 188 hours for Clustal-default, 78 for MAFFT-default, and 50 for MAFFT-dpparttree.FAMSA used below 8 GB of RAM, whereas MAFFT-dpparttree allocated 47 GB and MAFFT-default and Clustal Omega failed on a 128 GB machine.
- Classic benchmarks: On classic benchmarks, FAMSA was second among non-consistency methods on BAliBASE and PREFAB, third on OXBench-X, and first on SABmark.Execution-time results identified FAMSA as one of the fastest methods for low and moderately sized sets.
Discussion
FAMSA combines scalable computation with strong alignment quality on very large protein families, while its accuracy assessment and refinement strategy retain important boundaries.
- Scalability: FAMSA processed 415 519 sequences in less than 2 hours using less than 8 GB of RAM.Clustal Omega crashed after 2 days on 128 GB, whereas MAFFT used 47 GB and completed in 5 hours.
- Scope: FAMSA’s scalability in quality, time, and memory makes protein families of up to a million sequences applicable targets.The paper describes such families as a no-go area for competing software.
- Future development: Profile construction was a scalability bottleneck, motivating future parallelisation of dynamic programming and improved GPU or co-processor utilisation.
- Limitations: Iterative refinement is applied only to families with fewer than 1000 sequences because of computational costs.Applying limited refinement to larger sets remains a proposed direction.
- Limitations: Accuracy evaluation for 10 000 or more proteins is limited by reference sequences containing only a small fraction of family members.The authors identify new benchmarks with more reference sequences as needed.
Author contributions statement
The authors describe separate responsibilities for algorithm design, GPU development, implementation, benchmarking, experiments, and manuscript preparation.
- SD and ADG designed the main algorithm, while AG and SD designed the GPU component.
- AG and SD prepared the implementation and designed and prepared the new benchmark.
- SD performed the experiments, and SD, AG, and ADG drafted the manuscript and supplementary material.All authors read and approved the final manuscript.
Additional information
The supplementary material documents data preparation and experimental procedures, and the authors report no competing financial interests.
- The supplementary material contains details on data preparation and experimental procedures.
- The authors declare no competing financial interests.
Examined programs
The experiments used multiple alignment programs with specified command-line settings, including threaded, default, iterative-refinement, and tree-construction variants.
- The experimental programs and their running parameters are listed explicitly.
- Clustal Omega: Clustal Omega was evaluated with default, auto, and parttree configurations using eight threads.
- Command-line settings: The examined settings included quiet execution, input and output file arguments, and alternative tree or distance options.
- Other programs: Other tested configurations included dpparttree, default, maxiters2, and threaded command forms.The listed commands specify options such as --dpparttree, --maxiters 2, and thread counts.
Additional results
Table 4 compares algorithm performance on ExtHomFam datasets, with runtimes reported in hours, minutes, and seconds.
- Table 4 compares algorithms using ExtHomFam datasets.
- The table reports algorithm runtimes in hours:minutes:seconds format.
- The table is intended for cross-algorithm comparison across the ExtHomFam datasets.