Alexandra M. Carvalho

Research interests | Publications | Software | Teaching | Short CV


A parallel algorithm for the extraction of structured motifs

Alexandra M. Carvalho, Ana T. Freitas, Arlindo L. Oliveira and Marie-France Sagot
Proceedings of the 19th ACM Symposium on Applied Computing (SAC'04), pages 147-153
Nicosia, Cyprus, 2004

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.

Keywords: Bioinformatics, Suffix tree, Structured motifs, Grid computing, Parallel algorithm.

Availability: Two implementations of the PSMILE algorithm were developed, one using a computational grid infrastructure, the Globus Toolkit with MPICH-G2, and another one using the TreadMarks distributed shared memory system. The PSMILE source for any of these implementations can be requested by .

Get a preprint: [ps] [ps.gz] [pdf] [pdf.gz]
Get a bibentry: [bib] [bbl]


Research interests | Publications | Software | Teaching | Short CV