Multiple Sequence Alignment Using Three- Dimensional Fragments

Authors: Layal Al Ait, Eduardo Corel, Kifah Tout, Burkhard Morgenstern

Abstract:

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.

Keywords: DIALIGN, Multiple sequence alignment, Threedimensional fragments.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060076

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.