title: Parallel pattern identification in biological sequences on clusters.
abstract: Tandem repeats are ubiquitous sequence features in both prokaryotic and eukaryotic genomes. They are known to cause several inherited neurological diseases in humans. Identifying these patterns is a highly computation-intensive process. Previous parallel implementations use straightforward domain decomposition based on existing sequential algorithms and rely on parallel machines with low-latency interconnection network and fast hardware support for processor synchronization. Our research exploits the superior cost effectiveness and flexibility achieved through low-cost clusters to speed up biological computations by designing communication-efficient parallel algorithms for pattern identification. This paper presents a low communication-overhead parallel algorithm for pattern identification in biological sequences. Given a biological sequence of length n and a pattern of length m, we conclude an algorithm with five computation/communication phases, each requiring O(n) computation time and only O(p) message units. The low communication overhead of the algorithm is essential in achieving reasonable speedups on clusters, where the inter-processor communication latency is usually higher.
authors.affiliation: Department of Computer Science and Engineering, U-155, University of Connecticut, Storrs, CT 06269, USA. huang@cse.uconn.edu
authors.forename: Chun-Hsi
authors.initials: CH
authors.lastname: Huang
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D003195:Computer Communication Networks; D003205:Computing Methodologies; D020869:Gene Expression Profiling / Q000379:methods; D010363:Pattern Recognition, Automated; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020080:Tandem Repeat Sequences / Q000235:genetics*