Limits...
MTRAP: pairwise sequence alignment algorithm by a new measure based on transition probability between two consecutive pairs of residues.

Hara T, Sato K, Ohya M - BMC Bioinformatics (2010)

Bottom Line: Especially for the sequences with sequence identity less than 15%, our method improves the alignment accuracy significantly.We indicated that our method leads to a significant increase in alignment accuracy compared with other methods.The source code is available at our web page, whose address is found in the section "Availability and requirements".

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan. hara@is.noda.tus.ac.jp

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".

Show MeSH
The ratios of the average Q scores on the PREFAB 4.0 database. The upper two figures show the ratio of the average Q score by MTRAP to that by Needle and the ratio of ours to that by ClustalW2, both for PAM substitution matrix. The middle two figures show the ratios for BLOSUM substitution matrix. The last figure shows the ratio for GONNET substitution matrix.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2875243&req=5

Figure 3: The ratios of the average Q scores on the PREFAB 4.0 database. The upper two figures show the ratio of the average Q score by MTRAP to that by Needle and the ratio of ours to that by ClustalW2, both for PAM substitution matrix. The middle two figures show the ratios for BLOSUM substitution matrix. The last figure shows the ratio for GONNET substitution matrix.

Mentions: We did the performance evaluations using three different substitution matrix series: PAM, BLOSUM and GONNET, with HOMSTRAD and PREFAB 4.0, whose results are shown in Table 3 and Figure 3, respectively. We compared MTRAP with two typical global alignment programs, Needle and ClustalW2, which can use various substitution matrices. We used all 630 protein pairs of HOMSTRAD and all 1682 protein pairs of PREFAB 4.0. The similarity between the test alignment and the reference alignment was measured with the Q score.


MTRAP: pairwise sequence alignment algorithm by a new measure based on transition probability between two consecutive pairs of residues.

Hara T, Sato K, Ohya M - BMC Bioinformatics (2010)

The ratios of the average Q scores on the PREFAB 4.0 database. The upper two figures show the ratio of the average Q score by MTRAP to that by Needle and the ratio of ours to that by ClustalW2, both for PAM substitution matrix. The middle two figures show the ratios for BLOSUM substitution matrix. The last figure shows the ratio for GONNET substitution matrix.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2875243&req=5

Figure 3: The ratios of the average Q scores on the PREFAB 4.0 database. The upper two figures show the ratio of the average Q score by MTRAP to that by Needle and the ratio of ours to that by ClustalW2, both for PAM substitution matrix. The middle two figures show the ratios for BLOSUM substitution matrix. The last figure shows the ratio for GONNET substitution matrix.
Mentions: We did the performance evaluations using three different substitution matrix series: PAM, BLOSUM and GONNET, with HOMSTRAD and PREFAB 4.0, whose results are shown in Table 3 and Figure 3, respectively. We compared MTRAP with two typical global alignment programs, Needle and ClustalW2, which can use various substitution matrices. We used all 630 protein pairs of HOMSTRAD and all 1682 protein pairs of PREFAB 4.0. The similarity between the test alignment and the reference alignment was measured with the Q score.

Bottom Line: Especially for the sequences with sequence identity less than 15%, our method improves the alignment accuracy significantly.We indicated that our method leads to a significant increase in alignment accuracy compared with other methods.The source code is available at our web page, whose address is found in the section "Availability and requirements".

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan. hara@is.noda.tus.ac.jp

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".

Show MeSH