Multiple Sequence Alignment Using Three- Dimensional Fragments

Background: Dialign is a DNA/Protein alignment tool for performing pairwise and multiple pairwise alignments through the comparison of gap-free segments (fragments) between sequence pairs. An alignment of two sequences is a chain of fragments, i.e local gap-free pairwise alignments, with the highest total score. METHOD: A new approach is defined in this article which relies on the concept of using three-dimensional fragments – i.e. local threeway alignments -- in the alignment process instead of twodimensional ones. These three-dimensional fragments are gap-free alignments constituting of equal-length segments belonging to three distinct sequences. RESULTS: The obtained results showed good improvments over the performance of DIALIGN.

Authors:

• Layal Al Ait
• Eduardo Corel
• Kifah Tout
• Burkhard Morgenstern

Keywords:

• DIALIGN
• Multiple sequence alignment
• Threedimensional fragments.

References:

[1] Abdeddaim,S. and Morgenstern,B. (2001) Speeding up the DIALIGN
multiple alignment program by using the ÔÇÿgreedy alignment of biological
sequences library- (GABIOS-LIB). Lect. Notes Comput. Sci., 2066, 1-
11.
[2] Dayhoff,M.O., Schwartz,R.M. and Orcutt,B.C. (1978) A model of
evolutionary change in proteins. Atlas Protein Seq. Struct., 6,345-362.
[3] Henikoff,S. and Henikoff,J.G. (1994) Protein family classification based
on searching a database of blocks. Genomics, 19, 97-107.
[4] Morgenstern,B., Dress,A., Werner,T., (1996) Multiple DNA and protein
sequence alignment based on segment-to-segment comparison. Proc.
NAtl Acad. Sci USA, 93, 12098-12103.
[5] Morgenstern,B., French,K., Dress,A., Werner,T., (1998) DIALIGN:
Finding local similarities by multiple sequence alignment.
Bioinformatics, 14, 290-294.
[6] Morgenstern,B., Atchley,W.R., Hahn,K. and Dress,A. (1998) Seqmentbased
scores of pairwise and multiple sequence alignments. In
Glasgow,J., Littlejohn,T., Major,F., Lathrop,R, Sankoff,D. and
Sensen,C. (eds), Proceedings of the Sixth International Conference on
Intelligent Systems for Molecular Biology. AAAI Press, Menlo PArk,
CA,pp. 115-121.
[7] Morgenstern,B. (1999) DIALIGN 2: improvement of the segment-tosegment
approach to multiple sequence alignment. Bioinformatics, 15,
211-218.
[8] Morgenstern,B., Werner,N., Prohaska,S.J., Steinkamp,R., Schneider,I.,
Subramanian,A.R., Stadler,P.F. and Weyer-Menkhoff,J. (2005) Multiple
Sequence alignment with user-defined constraints at GOBICS.
Bioinformatics, 21, 1271-1273.
[9] Morgenstern,B., Prohaska,S.J., Po¨ hler,D. and Stadler,P.F. (2006)
Multiple sequence alignment with user-defined anchor points.
Algorithms for Molecular Biology, 1, 6.Corel,E., Pitschi,F. and
Morgenstern,B. (2010) A min-cut algorithm for the consistency problem
in multiple sequence alignment. Bioinformatics., 26, 1015-1021.
[10] Needleman,S. and Wunsch,C. (1970) A general method applicable to
the search for similarities in the amino acid sequences of two proteins. J.
Mol. Biol., 48, 443-453.
[11] Subramanian1,A.R., Weyer-Menkhoff,J., Kaufmann,M.,
Morgenstern,B., (2005) DIALIGN-T: An improved algorithm for
segment-based multiple sequence alignment. BMC Bioinformatics.
[12] Subramanian1,A.R., Hiran,S., Steinkamp,R., Meinicke,P.,Corel,E.,
Morgenstern,B., (2010) DIALIGN-TX and multiple protein alignment
using secondary structure information at GOBICS. Nucleic Acids
Research, 38, 19-22.
[13] Thompson,J.D., Koehl,P., Ripp,R. and Poch,O. (2005) BAliBASE 3.0:
latest developments of the multiple sequence alignment benchmark.
Proteins, 61, 127-136.
[14] E.Corel, F. Pitschi, B. Morgenstern (2010) A min-cut Algorithm for the
Consistency Problem in Multiple Sequence Alignment Bioinformatics
26, 1015-1021, doi:10.1093/bioinformatics/btq082.