An exact algorithm to identify motifs in orthologous sequences from multiple species.
The identification of sequence motifs is a fundamental method for suggesting good candidates for biologically functional regions such as promoters, splice sites, binding sites, etc. We investigate the following approach to identifying motifs: given a collection of orthologous sequences from multiple species related by a known phylogenetic tree, search for motifs that are well conserved (according to a parsimony measure) in the species. We present an exact algorithm for solving this problem. We then discuss experimental results on finding promoters of the rbcS gene for a family of 10 plants, on finding promoters of the adh gene for 12 Drosophila species, and on finding promoters of several chloroplast encoded genes.
Blanchette
M
M
Department of Computer Science and Engineering, University of Washington, Seattle 98195-2350, USA. blanchem@cs.washington.edu
Schwikowski
B
B
Tompa
M
M
D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D016678:Genome; D008969:Molecular Sequence Data; D011401:Promoter Regions, Genetic; D017421:Sequence Analysis / Q000379:methods*; D013045:Species Specificity