Kalign – an accurate and fast multiple sequence alignment algorithm

By Timo Lassmann, Erik L. L. Sonnhammer. BMC Bioinformatics, 2005

740 citations recorded by the source corpus.

BackgroundThe alignment of multiple protein sequences is a fundamental step in the analysis of biological data. It has traditionally been applied to analyzing protein families for conserved motifs, phylogeny, structural properties, and to improve sensitivity in homology searching. The availability of complete genome sequences has increased the demands on multiple sequence alignment (MSA) programs. Current MSA methods suffer from being either too inaccurate or too computationally expensive to be applied effectively in large-scale comparative genomics.ResultsWe developed Kalign, a method employing the Wu-Manber string-matching algorithm, to improve both the accuracy and speed of multiple sequence alignment. We compared the speed and accuracy of Kalign to other popular methods using Balibase, Prefab, and a new large test set. Kalign was as accurate as the best other methods on small alignments, but significantly more accurate when aligning large and distantly related sets of sequences. In our comparisons, Kalign was about 10 times faster than ClustalW and, depending on the alignment size, up to 50 times faster than popular iterative methods.ConclusionKalign is a fast and robust alignment method. It is especially well suited for the increasingly important task of aligning large numbers of sequences.

Subfields: Genetics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/b69ba6ce3b7f80bd41ef73dcf31b20c25cb40402

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

In Molecular Biology

Citations in the corpus

Accurate multiple sequence alignment of transmembrane proteins with PSI-Coffee (2012, neutral): “04 [17], PROMALS, MAFFT 6.”
Accessory proteins of SARS-CoV and other coronaviruses (2014, methodology): “Phylogenetic analysis of coronaviruses based on pp1ab using Kalign multiple sequence alignment and TreeDyn tree viewer (Chevenet et al., 2006; Lassmann and Sonnhammer, 2005).”
The accuracy of several multiple sequence alignment programs for proteins (2006, methodology): “Also, Kalign updates the positions of pattern matchings, which adjusts the absolute position of matches found within sequences to their relative positions within generated profiles [30].”
A revised taxonomic and phylogenetic concept for the planktonic foraminifer species Globigerinoides (2011, background): “03 (Lassmann and Sonnhammer, 2005), MUSCLE (Edgar, 2004), and MAFFT version 6.”
The MPI bioinformatics Toolkit as an integrative platform for advanced protein sequence and structure analysis (2016, methodology): “Of the external tools added to the Toolkit in recent years, most are multiple protein sequence alignment methods and include Clustal Omega (38), Kalign (39), MSAProbs (40), TCoffee (41) and GLProbs (42).”
A global averaging method for dynamic time warping, with applications to clustering (2011, neutral): “…for return m[S,T] Algorithm 2. first Require: p ¼ (a, b): couple return a Algorithm 3. second Require: p ¼ (a, b): couple return b Algorithm 4. minVal Require: v1, v2, v3: couple if firstðv1Þrminðfirstðv2Þ,firstðv3ÞÞ then return v1 else if firstðv2Þr firstðv3Þ then return v2 else return v3 end if”
Recent developments in the MAFFT multiple sequence alignment program (2008, methodology): “Clustal W [50, 51], MAFFT, POA [52], Kalign [53] and many other MSA packages use this method with various modifications.”
A new bioinformatics analysis tools framework at EMBL–EBI (2010, background): “These include sequence similarity search services (http://www.ebi.ac .uk/Tools/similarity.html), such as FASTA (3), BLAST (4,5) and InterProScan (6) and multiple sequence alignment tools (http://www.ebi.ac.uk/Tools/sequence.html), such as ClustalW (7), T-Coffee (8), MUSCLE (9), Kalign (10) and MAFFT”
Using inferred residue contacts to distinguish between correct and incorrect protein models (2008, methodology): “For those structures with at least 100 remaining homologs, alignments were constructed with either Kalign (Lassmann and Sonnhammer, 2005) or MUSCLE (Edgar, 2004).”
GENCODE: The reference human genome annotation for The ENCODE Project (2012, methodology): “Transcripts are aligned against related species using three different alignment methods, Kalign (Lassmann and Sonnhammer 2005), multiz (Blanchette et al. 2004), and PRANK (Loytynoja and Goldman 2005), and evolutionary rates of exons for each of the three alignments are contrasted using SLR (Massingh”
Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features (2008, methodology): “To find a good compromise between accuracy and computational efficiency, the original Kalign program (15) was optimized in many ways.”