Sequence alignment software

From Wikipedia, the free encyclopedia

This list of sequence alignment software is a compilation of bioinformatics software tools and web portals used in pairwise sequence alignment, multiple sequence alignment, and structural alignment.

Contents 1 Database search only 2 Pairwise alignment 3 Multiple sequence alignment 4 Structural alignment 5 Genomics analysis 6 Motif finding 7 Benchmarking 8 External links

[edit] Database search only

NAME	Description	Sequence Type*	Link
FASTA	k-tuple local search	Both	EBI GenomeNet PIR (protein only)
BLAST	k-tuple local search (Basic Local Alignment Search Tool)	Both	NCBI EBI GenomeNet PIR (protein only)
SSEARCH	Smith-Waterman search (more sensitive than FASTA)	Both	server
HMMer	Hidden Markov profile search	Protein/DNA	download (S. Eddy)
SAM	Hidden Markov profile search	Protein/DNA	SAM (K. Karplus, A. Krogh)
Combinatorial Extension	Structural alignment search	Protein	server
IDF	Inverse Document Frequency	Both	Download
*Sequence Type: Protein or nucleotide

[edit] Pairwise alignment

NAME	Description	Sequence Type*	Alignment Type**	Link	Author	Year
BLASTZ	Seeded pattern-matching	Nucleotide	Local	download	Schwartz et al.	2003
DNADot	Web-based dot-plot tool	Nucleotide	Global	server	R. Bowen	1998
DOTLET	Java-based dot-plot tool	Both	Global	applet	M. Pagni and T. Junier	1998
JAligner	Open source Java implementation of Smith-Waterman	Both	Local	JWS	A. Moustafa	2005
LALIGN	Local similarity (same algorithm as SIM)	Both	Local (default) or global	server	B. Pearson	1991 (algorithm)
matcher	Memory-optimized needleman but slow dynamic programming (based on LALIGN)	Both	Local	server	I. Longden (modified from B. Pearson)	1999
MCALIGN2	explicit models of indel evolution	DNA	Global	server	J. Wang et al.	2006
MUMmer	Suffix-Tree based	Nucleotide	Global	download	S. Kurtz et al.	2004
needle	Needleman-Wunsch dynamic programming	Both	Global	server	A. Bleasby	1999
PatternHunter	Seeded pattern-matching	Nucleotide	Local	download	B. Ma et al.	2002-2004
ProbA (also propA)	Stochastic partition function sampling via dynamic programming	Both	Global	download	U. Mückstein	2002
REPuter	Suffix-Tree based	Nucleotide	Local	download	S. Kurtz et al.	2001
SEQALN	Various dynamic programming	Both	Local or Global	server	M.S. Waterman and P. Hardy	1996
SIM, GAP, NAP, LAP	Local similarity with varying gap treatments	Both	Local or global	server	X. Huang and W. Miller	1990-6
SIM	Local similarity	Both	Local	servers	X. Huang and W. Miller	1991
SLIM Search	Ultra-fast blocked alignment	Both	Both	site	L. Bloksberg	2004
stretcher	Memory-optimized but slow dynamic programming	Both	Global	server	I. Longden (modified from G. Myers and W. Miller)	1999
tranalign	Aligns nucleic acid sequences given a protein alignment	Nucleotide	NA	server	G. Williams (modified from B. Pearson)	2002
water	Smith-Waterman dynamic programming	Both	Local	server	A. Bleasby	1999
wordmatch	k-tuple pairwise match	Both	NA	server	I. Longden	1998
YASS	Seeded pattern-matching	Nucleotide	Local	server download	L. Noe and G. Kucherov	2003-2006
*Sequence Type: Protein or nucleotide. **Alignment Type: Local or global

[edit] Multiple sequence alignment

NAME	Description	Sequence Type*	Alignment Type**	Link	Author	Year
DNA Baser	Multi alignment	Both	Local or Global + Post processing	[1]	M. Gabriel	released 2005
MSA	Dynamic programming	Both	Local or Global	download	D.J. Lipman et al.	1989 (modified 1995)
ABA	A-Bruijn alignment	Protein	Global	download	B.Raphaelet al.	2004
MULTALIN	Dynamic programming/clustering	Both	Local or Global	server	F. Corpet	1988
PSAlign	Alignment preserving non-heuristic	Both	Local or Global	download	S.H. Sze, Y. Lu, Q. Yang.	2006
ClustalW	Progressive alignment	Both	Local or Global	EBI PBIL EMBNet GenomeNet	Thompson et al.	1994
Kalign	Progressive alignment	Both	Global	serverEBI MPItoolkit	T. Lassmann	2005
T-Coffee	More sensitive progressive alignment	Both	Local or Global	server	C. Notredame et al.	2000
AMAP	Sequence annealing	Both	Global	server	A. Schwartz and L. Pachter	2006
MAVID	Progressive alignment	Both	Global	server	N. Bray and L. Pachter	2004
Multi-LAGAN	Progressive dynamic programming alignment	Both	Global	server	M. Brudno et al.	2003
MUSCLE	Progressive/iterative alignment	Both	Local or Global	server	R. Edgar	2004
MAFFT	Progressive/iterative alignment	Both	Local or Global	GenomeNet MAFFT	K. Katoh et al.	2005
Geneious	Progressive/Iterative alignment; ClustalW plugin	Both	Local or Global	download	A.J. Drummond et al.	2005 / 2006
CHAOS/DIALIGN	Iterative alignment	Both	Local (preferred)	server	M. Brudno and B. Morgenstern	2003
PRRN/PRRP	Iterative alignment (especially refinement)	Protein	Local or Global	PRRP PRRN	Y. Totoki (based on O. Gotoh)	1991 and later
POA	Partial order/hidden Markov model	Protein	Local or Global	download	C. Lee	2002
SAM	Hidden Markov model	Protein	Local or Global	server	A. Krogh et al.	1994 (most recent version 2002)
ProbCons	Probabilistic/consistency	Protein	Local or Global	server	C. Do et al.	2005
SAGA	Sequence alignment by genetic algorithm	Protein	Local or Global	download	C. Notredame et al.	1996 (new version 1998)
Ed'Nimbus	Seeded filtration	Nucleotides	Local	server	P. Peterlongo et al.	2006
RevTrans	Combines DNA and Protein alignment, by back translating the protein alignment to DNA.	DNA/Protein (special)	Local or Global	server	Wernersson and Pedersen	2003 (newest version 2005)
*Sequence Type: Protein or nucleotide. **Alignment Type: Local or global

[edit] Structural alignment

NAME	Description	Class	Type	Link	Author	Year
MAMMOTH	MAtching Molecular Models Obtained from Theory	Cα	Pair	server	AR. Ortiz	2002
CE/CE-MC	Combinatorial Extension -- Monte Carlo	Cα	Multi	server	I. Shindyalov	2000
DaliLite	Distance Matrix Alignment	C-Map	Pair	server download	L. Holm	1993
VAST	Vector Alignment Search Tool	SSE	Pair	server	S. Bryant	1996
PrISM	Protein Informatics Systems for Modeling	SSE	Multi	server	B. Honig	2000
SSAP	Sequential Structure Alignment Program	SSE	Multi	server	C. Orengo	1989
SARF2	Spatial Arrangements of Backbone Fragments	SSE	Pair	server	D. Fischer	1996
KENOBI/K2	NA	SSE	Pair	server	Z. Weng	2000
STAMP	STructural Alignment of Multiple Proteins	Cα	Multi	server	R. Russell and G. Barton	1992
MASS	Multiple Alignment by Secondary Structure	SSE	Multi	server	O. Dror and H. Wolfson	2003
MALECON	NA	Geometry	Multi	NA	S. Wodak	2004
MultiProt	Multiple Alignment of Protein Structures	Geometry	Multi	server	M. Shatsky and H. Wolfson	2004
SCALI	Structural Core ALIgnment of proteins	Sequence	Pair	server	C. Bystroff	2004
DEJAVU	NA	SSE	Pair	server	GJ. Kleywegt	1997
SSM	Secondary Structure Matching	SSE/Cα	Multi	server	E. Krissinel	2003
SHEBA	Structural Homology by Environment-Based Alignment	Sequence	Pair	server	B. Lee	2000
LGA	Local-Global Alignment	Cα	Pair	server	A. Zemla	2003
POSA	Partial Order Structure Alignment	Cα	Multi	server	Y. Ye and A. Godzik	2005
FATCAT	Flexible Structure AlignmenT by Chaining Aligned Fragment Pairs Allowing Twists	Cα	Pair	server	Y. Ye and A. Godzik	2004
Matras	MArkovian TRAnsition of protein Structure	Cα & SSE	Pair	NA	K. Nishikawa	2000
MAMMOTH-mult	MAMMOTH-based multiple structure alignment	Cα	Multi	server	D. Lupyan	2005
Protein3Dfit	NA	C-Map	Pair	server	D. Schomburg	1994
PRIDE	PRobaility of IDEntity	Cα	Pair	server	S. Pongor	2002
FAST	FAST Alignment and Search Tool	Cα	Pair	server	J. Zhu	2004
C-BOP	Coordinate-Based Organization of Proteins	N/A	Multi	server	E. Sandelin	2005
ProFit	Protein least-squares Fitting	Cα	Multi	server	ACR. Martin	1996
TOPOFIT	Alignment as a superimposition of common volumes at a topomax point	Cα	Pair	server	V. A. Ilyin	2004
MUSTANG	MUltiple STructural AligNment AlGorithm	Cα & C-Map	Multi	download	A.S. Konagurthu et al.	2005
URMS	Unit-vector RMSD	Cα	Pair	server	K. Kedem	2003
LOCK	Hierarchical protein structure superposition	SSE	Pair	NA	AP. Singh	1997
LOCK 2	Improvements over LOCK	SSE	Pair	NA	J. Shapiro	2003
CBA	Consistency Based Alignment	SSE	Multi	download	J. Ebert	2006
TetraDA	Tetrahedral Decomposition Alignment	SSE	Multi	NA	J. Roach	2005
STRAP	STRucture based Alignment Program	Cα	Multi	server	C. Gille	2006
LOVOALIGN	Low Order Value Optimization methods for Structural Alignment	Cα	Multi	server	Andreani et al.	2006
GANGSTA	Genetic Algorithm for Nonsequential and Gapped STructural Alignment	SSE/C-Map	Multi	server	B Kolbeck, P May, T Schmidt-Gönner, EW Knapp	2006
CURVE	NA	Geometry	Multi	NA	D. Zhi	2006
TM-align	TM-score based protein structure alignment	Cα	Pair	server	Y. Zhang, J. Skolnick	2005
MatAlign	Protein Structure Comparison by Matrix Alignment	C-Map	Pair	site	Z. Aung and K.L. Tan	2006
Vorolign	Fast structure alignment using Voronoi contacts	Voronoi contacts	Multi	server	Birzele F, Gewehr J E, Csaba G, Zimmer R	2007
EXPRESSO	Fast Multiple Structural Alignment using T-Coffee and Sap	Cα	Multi	[2]	Notredame et al.	2007
CAALIGN	Cα Align	Cα	Multi	site	T.J. Oldfield	2007
Key map: Cα -- Backbone Atom (Cα) Alignment; SSE -- Secondary Structure Elements Alignment; Pair -- Pairwise Alignment (2 structures *only*); Multi -- Multiple Structure Alignment (MStA); C-Map -- Contact Map

[edit] Genomics analysis

NAME	Description	Sequence Type*	Link
SLAM	Gene finding, alignment, annotation (human-mouse homology identification)	Nucleotide	server
Mauve	Multiple alignment of rearranged genomes	Nucleotide	download
MGA	Multiple Genome Aligner	Nucleotide	download
Mulan	Local multiple alignments of genome-length sequences	Nucleotide	server
Sequerome	Profiling sequence alignment data with major servers/services	Nucleotide/peptide	[3]
AVID	Pairwise global alignment with whole genomes	Nucleotide	server
SIBsim4 / Sim4	A program designed to align an expressed DNA sequence with a genomic sequence, allowing for introns	Nucleotide	download
Shuffle-LAGAN	Pairwise glocal alignment of completed genome regions	Nucleotide	server
*Sequence Type: Protein or nucleotide

[edit] Motif finding

NAME	Description	Sequence Type*	Link
MEME/MAST	Motif discovery and search	Both	server
BLOCKS	Ungapped motif identification from BLOCKS database	Both	server
eMOTIF	Extraction and identification of shorter motifs	Both	servers
Gibbs motif sampler	Stochastic motif extraction by statistical likelihood	Both	server (one of many implementations)
TEIRESIAS	Motif extraction and database search	Both	server
PRATT	Pattern generation for use with ScanProsite	Protein	server
ScanProsite	Motif database search tool	Protein	server
PHI-Blast	Motif search and alignment tool	Both	server
I-sites	Local structure motif library	Protein	server
*Sequence Type: Protein or nucleotide

[edit] Benchmarking

NAME	Link	Authors
BAliBASE	download	Thompson, Plewniak, Poch
Prefab	download	Edgar

[edit] External links

• Pollard et al. (2004) (PubMed Central free fulltext): The authors discuss LAGAN, CHAOS, and Dialign as the most effective tools tested for certain uses.