MTRAP: pairwise sequence alignment algorithm by a new measure based on transition probability between two consecutive pairs of residues.
BACKGROUND
Sequence alignment is one of the most important techniques to analyze biological systems. It is also true that the alignment is not complete and we have to develop it to look for more accurate method. In particular, an alignment for homologous sequences with low sequence similarity is not in satisfactory level. Usual methods for aligning protein sequences in recent years use a measure empirically determined. As an example, a measure is usually defined by a combination of two quantities (1) and (2) below: (1) the sum of substitutions between two residue segments, (2) the sum of gap penalties in insertion/deletion region. Such a measure is determined on the assumption that there is no an intersite correlation on the sequences. In this paper, we improve the alignment by taking the correlation of consecutive residues.


RESULTS
We introduced a new method of alignment, called MTRAP by introducing a metric defined on compound systems of two sequences. In the benchmark tests by PREFAB 4.0 and HOMSTRAD, our pairwise alignment method gives higher accuracy than other methods such as ClustalW2, TCoffee, MAFFT. Especially for the sequences with sequence identity less than 15%, our method improves the alignment accuracy significantly. Moreover, we also showed that our algorithm works well together with a consistency-based progressive multiple alignment by modifying the TCoffee to use our measure.


CONCLUSIONS
We indicated that our method leads to a significant increase in alignment accuracy compared with other methods. Our improvement is especially clear in low identity range of sequences. The source code is available at our web page, whose address is found in the section "Availability and requirements".
Hara
Toshihide
T
Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan. hara@is.noda.tus.ac.jp
Sato
Keiko
K
Ohya
Masanori
M
D000465:Algorithms; D001483:Base Sequence; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
J Mol Biol. 1995 Apr 7;247(4):536-40
7723011
Nucleic Acids Res. 2002 Jul 15;30(14):3059-66
12136088
Proc Natl Acad Sci U S A. 1989 Jun;86(12):4412-5
2734293
Science. 1973 Jul 20;181(4096):223-30
4124164
J Mol Biol. 1970 Mar;48(3):443-53
5420325
In Silico Biol. 2006;6(4):321-39
16922695
Bull Math Biol. 1990;52(4):509-25
1697773
J Mol Evol. 1987;25(4):351-60
3118049
Proteins. 2000 Jul 1;40(1):6-22
10813826
Biochem Biophys Res Commun. 1994 Mar 15;199(2):489-96
8135790
Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
7984417
Bioinformatics. 2006 Nov 15;22(22):2715-21
16954142
Bioinformatics. 2007 Nov 1;23(21):2947-8
17846036
Nucleic Acids Res. 2004 Jan 1;32(Database issue):D203-7
14681395
Proteins. 2005 Oct 1;61(1):127-36
16044462
Nucleic Acids Res. 2009 Feb;37(2):463-72
19056820
J Mol Biol. 2000 Sep 8;302(1):205-17
10964570
Bioinformatics. 1999 Mar;15(3):211-8
10222408
Trends Genet. 2000 Jun;16(6):276-7
10827456
BMC Bioinformatics. 2006 Aug 17;7:385
16916457
Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8
3162770
Nucleic Acids Res. 1999 Jul 1;27(13):2682-90
10373585
Genome Res. 2005 Feb;15(2):330-40
15687296
Bioinformatics. 2005 Oct 1;21(19):3704-10
16123116
Protein Sci. 1998 Nov;7(11):2469-71
9828015
Bioinformatics. 2005 Apr 1;21(7):1267-8
15333456
J Mol Biol. 1990 Oct 5;215(3):403-10
2231712
Nucleic Acids Res. 2004 Mar 19;32(5):1792-7
15034147
J Mol Biol. 1991 Jun 5;219(3):555-65
2051488