Exact Algorithms for Planted Motif Problems
Authors:
- 1 October 2005
- journal article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 12 (8) , 1117-1128
Abstract
The problem of identifying meaningful patterns (i.e., motifs) from biological data has been studied extensively due to its paramount importance. Three versions of this problem have been identified in the literature. One of these three problems is the planted (l, d)-motif problem. Several instances of this problem have been posed as a challenge. Numerous algorithms have been proposed in the literature that address this challenge. Many of these algorithms fall under the category of heuristic algorithms. In this paper we present algorithms for the planted (l, d)-motif problem that always find the correct answer(s). Our algorithms are very simple and are based on some ideas that are fundamentally different from the ones employed in the literature. We believe that the techniques we introduce in this paper will find independent applications.Keywords
This publication has 10 references indexed in Scilit:
- EFFICIENT RECONSTRUCTION OF HAPLOTYPE STRUCTURE VIA PERFECT PHYLOGENYJournal of Bioinformatics and Computational Biology, 2003
- Finding motifs in the twilight zoneBioinformatics, 2002
- Identifying DNA and protein patterns with statistically significant alignments of multiple sequences.Bioinformatics, 1999
- Predicting Gene Regulatory Elements in Silico on a Genomic ScaleGenome Research, 1998
- Extracting regulatory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies 1 1Edited by G. von HeijneJournal of Molecular Biology, 1998
- Unsupervised learning of multiple motifs in biopolymers using expectation maximizationMachine Learning, 1995
- Detecting Subtle Sequence Signals: a Gibbs Sampling Strategy for Multiple AlignmentScience, 1993
- Rigorous pattern-recognition methods for DNA sequencesJournal of Molecular Biology, 1985
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952