Research indexJournal article
Efficient parallel algorithms for processing biological sequences
Rajasekaran, Ammar, Shin and 1 other
International Journal of Computer Applications in Technology1 Jan 2006
NobleIDark:/48914/w1/20260521/38395316DOI10.1504/ijcat.2006.010596
Efficient parallel algorithms for processing biological sequences
Rajasekaran, Ammar, Shin and 1 other · International Journal of Computer Applications in Technology · 2006 · Subscription
NobleIDark:/48914/w1/20260521/38395316DOI10.1504/ijcat.2006.010596
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
Abstract
Processing of biological sequences is a compute-intensive problem. The amount of data available in biology is so enormous that sequential techniques take a very long time to process them. In this paper, we present some parallel algorithms for biological data processing. We consider a scenario where the operations performed on the sequences are arbitrary. In particular, we assume that a sequential algorithm can be executed in parallel by a number of processors on an input consisting of a file of sequences to be processed. The goal is to process all these sequences as efficiently as possible. We present four parallel algorithms in this paper: Algorithms 1-4. Algorithm 1 is shown to be (1+α)-competitive with high probability for any fixed α>0 under suitable assumptions. Algorithm 2 is shown to be O(1)-competitive and Algorithm 3 is shown to be 2-competitive. We have experimentally compared the performance of these four algorithms and the results are presented.