Title: Efficient parallel algorithms for processing biological sequences

Authors: S. Rajasekaran, R. Ammar, D.G. Shin, G. Zhang

Addresses: Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA. ' Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA. ' Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA. ' Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA

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.

Keywords: approximation algorithms; biological sequences; BLAST; competitiveness; parallel processing; parallel algorithms.

DOI: 10.1504/IJCAT.2006.010596

International Journal of Computer Applications in Technology, 2006 Vol.26 No.3, pp.119 - 125

Published online: 07 Aug 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article