Algorithms for phylogenetic footprinting. Export

@article{Blanchette2004, abstract = {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.}, address = {Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA 98195-2350, USA. blanchem@cs.washington.edu}, author = {Blanchette, M. and Schwikowski, B. and Tompa, M.}, citeulike-article-id = {750071}, citeulike-linkout-0 = {http://dx.doi.org/10.1089/10665270252935421}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/12015878}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=12015878}, doi = {10.1089/10665270252935421}, issn = {1066-5277}, journal = {J Comput Biol}, keywords = {comparative, footprinting, genomic}, number = {2}, pages = {211--223}, posted-at = {2008-09-30 04:43:53}, priority = {2}, title = {Algorithms for phylogenetic footprinting.}, url = {http://dx.doi.org/10.1089/10665270252935421}, volume = {9}, year = {2002} }

TY - JOUR ID - Blanchette2004 L3 - citeulike-article-id:750071 N2 - 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. IS - 2 JF - J Comput Biol SN - 1066-5277 AD - Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA 98195-2350, USA. blanchem@cs.washington.edu EP - 223 TI - Algorithms for phylogenetic footprinting. VL - 9 SP - 211 KW - comparative KW - footprinting KW - genomic AU - Blanchette, M AU - Schwikowski, B AU - Tompa, M PY - 2002/// UR - http://dx.doi.org/10.1089/10665270252935421 ER -