Please use this identifier to cite or link to this item:
|Title:||Aligning biological sequences on distributed bus networks: A divisible load scheduling approach|
Divisible load theory(DLT)
|Source:||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. https://doi.org/10.1109/TITB.2005.855559|
|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 , in our rigorous simulation experiments to illustrate all the theoretical findings. © 2005 IEEE.|
|Source Title:||IEEE Transactions on Information Technology in Biomedicine|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 14, 2018
WEB OF SCIENCETM
checked on Feb 14, 2018
checked on Feb 20, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.