| Algorithms for phylogenetic footprinting. | |
| | |
MedLine Citation:
|
PMID: 12015878 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
Phylogenetic footprinting is a technique that identifies regulatory elements by finding unusually well conserved regions in a set of orthologous noncoding DNA sequences from multiple species. We introduce a new motif-finding problem, the Substring Parsimony Problem, which is a formalization of the ideas behind phylogenetic footprinting, and we present an exact dynamic programming algorithm to solve it. We then present a number of algorithmic optimizations that allow our program to run quickly on most biologically interesting datasets. We show how to handle data sets in which only an unknown subset of the sequences contains the regulatory element. Finally, we describe how to empirically assess the statistical significance of the motifs found. Each technique is implemented and successfully identifies a number of known binding sites, as well as several highly conserved but uncharacterized regions. The program is available at http://bio.cs.washington.edu/software.html. |
| | |
Authors:
|
Mathieu Blanchette; Benno Schwikowski; Martin Tompa |
Related Documents
:
|
22713168 - Tracing the evolution of chiropractic students' confidence in clinical and patient comm... 20859778 - Gifa v. 4: a complete package for nmr data set processing. 16211538 - Gromacs: fast, flexible, and free. 20397498 - An investigation of the ability of computerized axiography to reproduce occlusal contacts. 19539838 - The acgme outcome project in ophthalmology: practical recommendations for overcoming th... 12292328 - Teens could get new message on waiting for sex. sex education. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 9 ISSN: 1066-5277 ISO Abbreviation: J. Comput. Biol. Publication Date: 2002 |
Date Detail:
|
Created Date: 2002-05-17 Completed Date: 2002-10-04 Revised Date: 2006-11-15 |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 211-23 Citation Subset: IM |
Affiliation:
|
Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA 98195-2350, USA. blanchem@cs.washington.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Computational Biology DNA Footprinting / statistics & numerical data* Databases, Nucleic Acid Genes, Regulator Phylogeny* Software |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: The advantage of functional prediction based on clustering of yeast genes and its correlation with n...
Next Document: Finding motifs using random projections.