title: An efficient algorithm for the identification of structured motifs in DNA promoter sequences.
abstract: We propose a new algorithm for identifying cis-regulatory modules in genomic sequences. The proposed algorithm, named RISO, uses a new data structure, called box-link, to store the information about conserved regions that occur in a well-ordered and regularly spaced manner in the data set sequences. This type of conserved regions, called structured motifs, is extremely relevant in the research of gene regulatory mechanisms since it can effectively represent promoter models. The complexity analysis shows a time and space gain over the best known exact algorithms that is exponential in the spacings between binding sites. A full implementation of the algorithm was developed and made available online. Experimental results show that the algorithm is much faster than existing ones, sometimes by more than four orders of magnitude. The application of the method to biological data sets shows its ability to extract relevant consensi.
authors.affiliation: IST/INESC-ID, Rua Alves Redol, 9, 1000-029 Lisboa, Portugal. asmc@algos.inesc-id.pt
authors.forename: Alexandra M
authors.initials: AM
authors.lastname: Carvalho
authors.forename: Ana T
authors.initials: AT
authors.lastname: Freitas
authors.forename: Arlindo L
authors.initials: AL
authors.lastname: Oliveira
authors.forename: Marie-France
authors.initials: MF
authors.lastname: Sagot
mesh_terms: D000465:Algorithms; D001419:Bacteria / Q000235:genetics / Q000378:metabolism; D001665:Binding Sites / Q000235:genetics; D019295:Computational Biology / Q000379:methods*; D002373:Cyclic AMP Receptor Protein / Q000378:metabolism; D004247:DNA / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D012321:DNA-Directed RNA Polymerases / Q000378:metabolism; D006801:Humans; D020407:Internet; D011401:Promoter Regions, Genetic / Q000235:genetics*; D020218:Response Elements / Q000235:genetics*; D012441:Saccharomyces cerevisiae / Q000235:genetics / Q000378:metabolism; D012808:Sigma Factor / Q000378:metabolism; D014157:Transcription Factors / Q000378:metabolism
chemical_list: D002373:Cyclic AMP Receptor Protein; D012808:Sigma Factor; D014157:Transcription Factors; D004247:DNA; C081775:RNA polymerase sigma 70; D012321:DNA-Directed RNA Polymerases