A parallel algorithm for the extraction of structured motifs
See where this sits in the topic map →Summary AI-generated
- TL;DR
- We propose a parallel algorithm for the efficient extraction of binding-site consensus from genomic sequences.
- Problem
- Not specified in the abstract.
- Method
- Building on an existing approach, the algorithm extracts structured motifs—which consist of an ordered collection of boxes with specified sizes and spacings—by using a suffix tree as its fundamental data structure and partitioning the search space across loosely coupled processors.
- Results
- The approach achieves a linear speedup relative to the number of available processing units under conditions that are easily met, as verified by both theoretical and experimental analysis.
- Contributions
- Not specified in the abstract.
- Limitations
- Not specified in the abstract.
- Takeaways
- Both theoretical and experimental analyses confirm that partitioning the motif searching space enables a linear speedup across multiple processing units.
- Applications
- Not specified in the abstract.
- Topics
- Not specified in the abstract.
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
In this work we propose a parallel algorithm for the efficient extraction of binding-site consensus from genomic sequences. This algorithm, based on an existing approach, extracts structured motifs, that consist of an ordered collection of p ≥ 1 boxes with sizes and spacings between them specified by given parameters. The contents of the boxes, which represent the extracted motifs, are unknown at the start of the process and are found by the algorithm using a suffix tree as the fundamental data structure. By partitioning the structured motif searching space we divide the most demanding part of the algorithm by a number of processors that can be loosely coupled. In this way we obtain, under conditions that are easily met, a speedup that is linear on the number of available processing units. This speedup is verified by both theoretical and experimental analysis, also presented in this paper.