title: MTRAP: pairwise sequence alignment algorithm by a new measure based on transition probability between two consecutive pairs of residues.
abstract: 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".
authors.affiliation: Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan. hara@is.noda.tus.ac.jp
authors.forename: Toshihide
authors.initials: T
authors.lastname: Hara
authors.forename: Keiko
authors.initials: K
authors.lastname: Sato
authors.forename: Masanori
authors.initials: M
authors.lastname: Ohya
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
references.citation: J Mol Biol. 1995 Apr 7;247(4):536-40
references.pmid: 7723011
references.citation: Nucleic Acids Res. 2002 Jul 15;30(14):3059-66
references.pmid: 12136088
references.citation: Proc Natl Acad Sci U S A. 1989 Jun;86(12):4412-5
references.pmid: 2734293
references.citation: Science. 1973 Jul 20;181(4096):223-30
references.pmid: 4124164
references.citation: J Mol Biol. 1970 Mar;48(3):443-53
references.pmid: 5420325
references.citation: In Silico Biol. 2006;6(4):321-39
references.pmid: 16922695
references.citation: Bull Math Biol. 1990;52(4):509-25
references.pmid: 1697773
references.citation: J Mol Evol. 1987;25(4):351-60
references.pmid: 3118049
references.citation: Proteins. 2000 Jul 1;40(1):6-22
references.pmid: 10813826
references.citation: Biochem Biophys Res Commun. 1994 Mar 15;199(2):489-96
references.pmid: 8135790
references.citation: Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
references.pmid: 7984417
references.citation: Bioinformatics. 2006 Nov 15;22(22):2715-21
references.pmid: 16954142
references.citation: Bioinformatics. 2007 Nov 1;23(21):2947-8
references.pmid: 17846036
references.citation: Nucleic Acids Res. 2004 Jan 1;32(Database issue):D203-7
references.pmid: 14681395
references.citation: Proteins. 2005 Oct 1;61(1):127-36
references.pmid: 16044462
references.citation: Nucleic Acids Res. 2009 Feb;37(2):463-72
references.pmid: 19056820
references.citation: J Mol Biol. 2000 Sep 8;302(1):205-17
references.pmid: 10964570
references.citation: Bioinformatics. 1999 Mar;15(3):211-8
references.pmid: 10222408
references.citation: Trends Genet. 2000 Jun;16(6):276-7
references.pmid: 10827456
references.citation: BMC Bioinformatics. 2006 Aug 17;7:385
references.pmid: 16916457
references.citation: Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8
references.pmid: 3162770
references.citation: Nucleic Acids Res. 1999 Jul 1;27(13):2682-90
references.pmid: 10373585
references.citation: Genome Res. 2005 Feb;15(2):330-40
references.pmid: 15687296
references.citation: Bioinformatics. 2005 Oct 1;21(19):3704-10
references.pmid: 16123116
references.citation: Protein Sci. 1998 Nov;7(11):2469-71
references.pmid: 9828015
references.citation: Bioinformatics. 2005 Apr 1;21(7):1267-8
references.pmid: 15333456
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: Nucleic Acids Res. 2004 Mar 19;32(5):1792-7
references.pmid: 15034147
references.citation: J Mol Biol. 1991 Jun 5;219(3):555-65
references.pmid: 2051488