Helmholtz Gemeinschaft


Suboptimal local alignments across multiple scoring schemes

Item Type:Article
Title:Suboptimal local alignments across multiple scoring schemes
Creators Name:Michael, M. and Dieterich, C. and Stoye, J.
Abstract:Sequence alignment algorithms have a long standing tradition in bioinformatics. In this paper, we formulate an extension to existing local alignment algorithms: local alignments across multiple scoring functions. For this purpose, we use the Waterman-Eggert algorithm for suboptimal local alignments as template and introduce two new features therein: 1) an alignment of two strings over a set of score functions and 2) a switch cost function delta for penalizing jumps into a different scoring scheme within an alignment. Phylogenetic footprinting, as one potential application of this algorithm, was studied in greater detail. In this context, the right evolutionary distance and thus the scoring scheme is often not known a priori. We measured sensitivity and specificity on a test set of 21 human-rodent promoter pairs. Ultimately, we could attain a 4.5-fold enrichment of verified binding sites in our alignments.
Keywords:Sequence Alignment, Non-parametric Alignment, Phylogenetic Footprinting, Comparative Sequence Analysis
Source:Lecture Notes in Computer Science
Series Name:Lecture Notes in Computer Science
Title of Book:Algorithms in Bioinformatics, Proceedings
Page Range:99-110
Number of Pages:476
Official Publication:https://doi.org/10.1007/b100405

Repository Staff Only: item control page

Open Access
MDC Library