A HIGHLY SCALABLE ALGORITHM FOR THE EXTRACTION OF CIS-REGULATORY REGIONS
See where this sits in the topic map →Summary AI-generated
- TL;DR
- We propose a highly scalable algorithm for identifying cis-regulatory modules and structured motifs in genomic sequences.
- Problem
- Existing algorithms struggle to efficiently identify structured motifs—collections of conserved regions with specific sizes and spacings—which are essential for representing promoter models in gene regulation research.
- Method
- The algorithm introduces a new data structure called 'box-link' to store information about conserved regions that occur in a well-ordered and regularly spaced manner across sequences.
- Results
- Complexity analysis demonstrates an exponential gain in time and space over previous algorithms based on the spacings between binding sites. Experiments show the algorithm is much faster than existing methods, sometimes by over two orders of magnitude.
- Contributions
- A novel, highly scalable algorithm and data structure for extracting structured motifs that outperforms previous approaches in speed and memory efficiency.
- Limitations
- Not specified in the abstract.
- Takeaways
- The proposed method successfully extracts relevant consensus sequences from biological datasets while offering significant performance improvements.
- Applications
- Analysis of biological datasets to extract relevant gene regulatory motifs and promoter models.
- Topics
- Computational biology, genomics, motif extraction, cis-regulatory modules
- For industry
- Biotechnology and genomics.
- Why it matters
- Advances computational methods for gene regulatory research by significantly improving the scalability and efficiency of motif extraction.
Abstract
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. 1.