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 :
16130468 - A note on endog: a computer program for analysing pedigree information.
22726308 - Comparison of communication skills between medical students admitted after interviews o...
2832828 - Fragmap--a program for restriction site map comparison.
7826878 - Use of harvard graphics program in processing of the results obtained from investigatio...
9105498 - The acquisition of life skills through adventure-based activities and programs: a revie...
1711428 - Aids education for patients with chronic mental illness.
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.