Introduction

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.

Publications

  1. An efficient algorithm for the identification of structured motifs in DNA promoter sequences.
    Cite this
    Carvalho AM, Freitas AT, Oliveira AL, Sagot MF, 2006-04-01 - IEEE/ACM transactions on computational biology and bioinformatics

Credits

  1. Alexandra M Carvalho
    Developer

    IST/INESC-ID, Rua Alves Redol

  2. Ana T Freitas
    Developer

  3. Arlindo L Oliveira
    Developer

  4. Marie-France Sagot
    Investigator

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT000736
Tool TypeApplication
Category
PlatformsLinux/Unix
TechnologiesC
User InterfaceTerminal Command Line
Download Count0
Submitted ByMarie-France Sagot