Please use this identifier to cite or link to this item:
Title: Aligning biological sequences on distributed bus networks: A divisible load scheduling approach
Authors: Min, W.H.
Veeravalli, B. 
Keywords: Biological sequences
Communication time
Divisible load theory(DLT)
Sequence alignment
Smith-Waterman algorithm
Issue Date: Dec-2005
Citation: Min, W.H., Veeravalli, B. (2005-12). Aligning biological sequences on distributed bus networks: A divisible load scheduling approach. IEEE Transactions on Information Technology in Biomedicine 9 (4) : 489-501. ScholarBank@NUS Repository.
Abstract: In this paper, we design a multiprocessor strategy that exploits the computational characteristics of the algorithms used for biological sequence comparison proposed in the literature. We employ divisible load theory (DLT) that is suitable for handling large scale processing on network based systems. For the first time in the domain of DLT, the problem of aligning biological sequences is attempted. The objective is to minimize the total processing time of the alignment process. In designing our strategy, DLT facilitates a clever partitioning of the entire computation process involved in such a way that the overall time consumed for aligning the sequences is a minimum. The partitioning takes into account the computation speeds of the nodes and the underlying communication network. Since this is a real-life application, the post-processing phase becomes important, and hence we consider propagating the results back in order to generate an exact alignment. We consider several cases in our analysis such as deriving closed-form solutions for the processing time for heterogeneous, homogeneous, and networks with slow links. Further, we attempt to employ a multiinstallment strategy to distribute the tasks such that a higher degree of parallelism can be achieved. For slow networks, our strategy recommends near-optimal solutions. We derive an important condition to identify such cases and propose two heuristic strategies. Also, our strategy can be extended for multisequence aligmnent by utilizing a clustering strategy such as the Berger-Munson algorithm proposed in the literature. Finally, we use real-life DNA samples of house mouse mitochondrion (Mus Musculus Mitochondrion, NC_001569) consisting of 16 295 residues and the DNA of human mitochondrion (Homo Sapiens Mitochondrion, NC_001807) consisting of 16 571 residues, obtainable from the GenBank [1], in our rigorous simulation experiments to illustrate all the theoretical findings. © 2005 IEEE.
Source Title: IEEE Transactions on Information Technology in Biomedicine
ISSN: 10897771
DOI: 10.1109/TITB.2005.855559
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Aug 8, 2022


checked on Aug 8, 2022

Page view(s)

checked on Aug 4, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.