| A cost-aggregating integer linear program for motif finding. | |
| | |
MedLine Citation:
|
PMID: 22081765 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
In the motif finding problem one seeks a set of mutually similar substrings within a collection of biological sequences. This is an important and widely-studied problem, as such shared motifs in DNA often correspond to regulatory elements. We study a combinatorial framework where the goal is to find substrings of a given length such that the sum of their pairwise distances is minimized. We describe a novel integer linear program for the problem, which uses the fact that distances between substrings come from a limited set of possibilities allowing for aggregate consideration of sequence position pairs with the same distances. We show how to tighten its linear programming relaxation by adding an exponential set of constraints and give an efficient separation algorithm that can find violated constraints, thereby showing that the tightened linear program can still be solved in polynomial time. We apply our approach to find optimal solutions for the motif finding problem and show that it is effective in practice in uncovering known transcription factor binding sites. |
| | |
Authors:
|
Carl Kingsford; Elena Zaslavsky; Mona Singh |
Related Documents
:
|
11168475 - Local cd-rom in interaction with html documents over the internet. 15566045 - Speeding up learning: accelerated distance learning in rehabilitation education. 15816205 - Evaluation of a distance-learning immunology and pathology module in a postgraduate bio... 21828295 - Dental students' attitudes toward underserved populations across four years of dental s... 16646385 - Thinking broadly about costs and benefits in ecological management. 22093575 - The roles and functions of safety professionals in taiwan: comparing the perceptions of... |
Publication Detail:
|
Type: JOURNAL ARTICLE |
Journal Detail:
|
Title: Journal of discrete algorithms (Amsterdam, Netherlands) Volume: 9 ISSN: 1570-8675 ISO Abbreviation: - Publication Date: 2011 Dec |
Date Detail:
|
Created Date: 2011-11-14 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101560679 Medline TA: J Discrete Algorithms (Amst) Country: - |
Other Details:
|
Languages: ENG Pagination: 326-334 Citation Subset: - |
Affiliation:
|
Center for Bioinformatics & Computational Biology and Department of Computer Science, University of Maryland, College Park, MD. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
| Grant Support | |
ID/Acronym/Agency:
|
R01 GM076275-01//NIGMS NIH HHS |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Theoretical Analysis the Optical Properties of Multi-coupled Silver Nanoshell Particles.
Next Document: Choice of Biologic Therapy for Patients with Rheumatoid Arthritis: The Infection Perspective.