An efficient algorithm for the identification of structured motifs in DNA promoter sequences.
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.
Carvalho
Alexandra M
AM
IST/INESC-ID, Rua Alves Redol, 9, 1000-029 Lisboa, Portugal. asmc@algos.inesc-id.pt
Freitas
Ana T
AT
Oliveira
Arlindo L
AL
Sagot
Marie-France
MF
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
D002373:Cyclic AMP Receptor Protein; D012808:Sigma Factor; D014157:Transcription Factors; D004247:DNA; C081775:RNA polymerase sigma 70; D012321:DNA-Directed RNA Polymerases