Affordable Access

Access to the full text

DIALIGN-TX: greedy and progressive approaches for segment-based multiple sequence alignment

Authors
  • Subramanian, Amarendran R1
  • Kaufmann, Michael1
  • Morgenstern, Burkhard2
  • 1 University of Tübingen, Wilhelm-Schickard-Institut für Informatik, Sand 13, Tübingen, 72076, Germany , Tübingen
  • 2 University of Göttingen, Institute of Microbiology and Genetics, Goldschmidtstr. 1, Göttingen, 37077, Germany , Göttingen
Type
Published Article
Journal
Algorithms for Molecular Biology
Publisher
BioMed Central
Publication Date
May 27, 2008
Volume
3
Issue
1
Identifiers
DOI: 10.1186/1748-7188-3-6
Source
Springer Nature
Keywords
License
Green

Abstract

BackgroundDIALIGN-T is a reimplementation of the multiple-alignment program DIALIGN. Due to several algorithmic improvements, it produces significantly better alignments on locally and globally related sequence sets than previous versions of DIALIGN. However, like the original implementation of the program, DIALIGN-T uses a a straight-forward greedy approach to assemble multiple alignments from local pairwise sequence similarities. Such greedy approaches may be vulnerable to spurious random similarities and can therefore lead to suboptimal results. In this paper, we present DIALIGN-TX, a substantial improvement of DIALIGN-T that combines our previous greedy algorithm with a progressive alignment approach.ResultsOur new heuristic produces significantly better alignments, especially on globally related sequences, without increasing the CPU time and memory consumption exceedingly. The new method is based on a guide tree; to detect possible spurious sequence similarities, it employs a vertex-cover approximation on a conflict graph. We performed benchmarking tests on a large set of nucleic acid and protein sequences For protein benchmarks we used the benchmark database BALIBASE 3 and an updated release of the database IRMBASE 2 for assessing the quality on globally and locally related sequences, respectively. For alignment of nucleic acid sequences, we used BRAliBase II for global alignment and a newly developed database of locally related sequences called DIRM-BASE 1. IRMBASE 2 and DIRMBASE 1 are constructed by implanting highly conserved motives at random positions in long unalignable sequences.ConclusionOn BALIBASE3, our new program performs significantly better than the previous program DIALIGN-T and outperforms the popular global aligner CLUSTAL W, though it is still outperformed by programs that focus on global alignment like MAFFT, MUSCLE and T-COFFEE. On the locally related test sets in IRMBASE 2 and DIRM-BASE 1, our method outperforms all other programs while MAFFT E-INSi is the only method that comes close to the performance of DIALIGN-TX.

Report this publication

Statistics

Seen <100 times