Research interests | Publications | Software | Teaching | Short CV
A highly scalable algorithm for the extraction of cis-regulatory regions
Alexandra M. Carvalho, Ana T. Freitas, Arlindo L. Oliveira and Marie-France Sagot
Proceedings of the 3rd Asia Pacific Bioinformatics Conference (APBC'05)
Volume 1 of Advances in Bioinformatics and Computational Biology (ABCB), pages 273-282
Singapore, 2005
In this paper we propose a new algorithm for identifying cis-regulatory modules in genomic sequences. In particular, the algorithm extracts structured motifs, defined as a collection of highly conserved regions with pre-specified sizes and spacings between them. This type of motifs is extremely relevant in the research of gene regulatory mechanisms since it can effectively represent promoter models. The proposed algorithm 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 dataset sequences. The complexity analysis shows a time and space gain over previous algorithms that is exponential on the spacings between binding sites. Experimental results show that the algorithm is much faster than existing ones, sometimes by more than two orders of magnitude. The application of the method to biological datasets shows its ability to extract relevant consensi.
Keywords: Box-link, Factor tree, Structured motif, Promoter, Complexity.
Availability: http://kdbio.inesc-id.pt/~asmc/software/riso.html
Get a preprint:
[ps]
[ps.gz]
[pdf]
[pdf.gz]
Get a bibentry:
[bib]
[bbl]
Research interests | Publications | Software | Teaching | Short CV