Learning Scoring Schemes for Sequence Alignment from Partial Examples

doi:10.1109/TCBB.2008.57

Return

Learning Scoring Schemes for Sequence Alignment from Partial Examples

2008-10-01

PRE

Eagu Kim *

John Kececioglu

DOI：10.1109/TCBB.2008.57

Original

Original request for help

Save

Abstract

En 中文

When aligning biological sequences, the choice of scoring scheme is critical. Even small changes in gap penalties, for example, can yield radically different alignments. A rigorous way to learn parameter values that are appropriate for biological sequences is through inverse parametric sequence alignment. Given a collection of examples of biologically correct reference alignments, this is the problem of finding parameter values that make the scores of the reference alignments be as close as possible to those of optimal alignments of their sequences. We extend prior work on inverse parametric alignment to partial examples, which contain regions where the reference alignment is not specified, and to an improved formulation based on minimizing the average error between the scores of the reference alignments and the scores of optimal alignments. Experiments on benchmark biological alignments show we can learn scoring schemes that generalize across protein families, and that boost the accuracy of multiple sequence alignment by as much as 25 percent.

Keywords:

Inverse parametric sequence alignment

substitution score matrices

affine gap penalties

linear programming

cutting plane algorithms

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.