Document Detail


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.
24047948 - Assessment of the efficacy of a hearing screening program for college students.
19539838 - The acgme outcome project in ophthalmology: practical recommendations for overcoming th...
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.