Optimizing amino acid substitution matrices with a local alignment kernel
[paper]
Hiroto Saigo, Jean-Philippe Vert and Tatsuya Akutsu
BMC Bioinformatics 7(246), 1-12, 2006
Abstract
Detecting remote homologies by direct comparison of protein sequences remains a challenging task. We had previously developed a similarity score between sequences, called a local alignment kernel, that exhibits good performance for this task in combination with asupport vector machine. The local alignment kernel depends on an amino acid substitution matrix. Since commonly used BLOSUM or PAM matrices for scoring amino acid matches have been optimized to be used in combination with the Smith-Waterman algorithm the matrices optimal for the local alignment kernel can be different.
Contrary to the local alignment score computed by the Smith-Waterman algorithm the local alignment kernel is differentiable with repect to the amino acid substitution and its derivatives can be computed efficiently by dynamic programmin. We optimized the substitution matrix by cllasical gradient descent by setting an objective function that measures how well the local alignment kernel discriminates homologs from non-homologs in the COG databse. The local alignment kernel exhibits better performance whe it used the matrices and gap parameters optimized by this procedure than when it used the matrices optimized for the Smith-Waterman algorithm. Furthremore, the matrices and gap parameters optimized for the local alignment kernel can also be used successfully by the Smith-Waterman algorithm.
This optimization procedure leads to useful substitution matrices, both for the local alignment kernel and the Smith-Waterman algorithm. The best performance for homology detection is obtained by the local alignment kernel.
Code LAkernel_d-0.1.3.tar.gz
For local alignment kernel, please visit this page.