The week's pick
Reseach Article
Load Balancing for Parallel Motif Discoveries
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 124 - Number 13 |
| Year of Publication: 2015 |
| Authors: Angkul Kongmunvattana |
10.5120/ijca2015905745
|
Angkul Kongmunvattana . Load Balancing for Parallel Motif Discoveries. International Journal of Computer Applications. 124, 13 ( August 2015), 29-34. DOI=10.5120/ijca2015905745
Abstract
The problem of motif discovery has been studied extensively over the last few decades. Many sequential and parallel algorithms have been proposed and studied. A significant runtime is still required for several challenging instances of the motif search problem. This paper studies parameter spaces to find an optimal point for load balancing between the master and the worker processes, which are collaboratively and concurrently searching for motifs. Extensive experiments have been carried out on the state-of-the-art TACC Stampede System. The results demonstrated that a workload from the parallel motif discovery problem is best divided between the master and worker processes by having the master process worked on the first ((l-4))/2 nucleotides in the DNA sequences, where l is the total length of the input DNA sequences, before passing the remaining work to the worker process. In addition, the results also shown that the latency tolerance techniques used in the implementation of this work is effective because of the almost linear speedup obtained.
References
- P. D’haeseleer, “What are DNA sequence motifs?” Nature Biotechnology, vol. 24, pp. 423-425, 2006.
- P. A. Pevzner and S.-H. Sze, “Combinatorial approaches to finding subtle signals in DNA sequences,” In Proceedings of the 8th Int’l Conference on Intelligent Systems for Molecular Biology, pp. 269-278, 2000.
- M. K. Das and H. K. Dai, “A survey of DNA motif finding algorithms,” BMC Bioinformatics, vol. 8, 2007.
- M. Nicolae and S. Rajasekaran, “qPMS9: An efficient algorithm for quorum planted motif search,” Nature Scientific Reports, vol. 5, 2015.
- S. Rajasekaran, S. Balla, and C.-H. Huang, “Exact algorithms for planted motif problems,” Journal of Computational Biology, 12(8), pp. 1117-1128, 2005.
- J. Davila, S. Balla, and S. Rajasekaran, “Fast and practical algorithms for planted (l,d) motif search,” IEEE Transactions on Computational Biology and Bioinformatics, vol. 4, no. 4., pp. 544-552, 2007.
- S. Rajasekaran and H. Dinh, “A speedup technique for (l,d)-motif finding algorithms,” BMC Research Notes, 4:54, 2011.
- Q. Yu, H. Huo, Y. Zhang, and H. Guo, “PairMotif: A new pattern-driven algorithm for planted (l,d) DNA motif search,” PLoS ONE, 7(10):e48442, 2012.
- S. Bandyopadhyay, S. Sahni, and S. Rajasekaran, “PMS6: A fast algorithm for motif discovery,” In Proceedings of the 2nd IEEE International Conference on Computational Advances in Bio and Medical Sciences, pp. 1-6, 2012.
- M. Nicolae and S. Rajasekaran, “Efficient sequential and parallel algorithms for planted motif search,” BMC Bioinformatics, 15:34, 2014.
- S. Sarkar, G. R. Kulkarni, P. P. Pande, and A. Kalyanaraman, “Network-on-chip hardware accelerators for biological sequence alignment,” IEEE Transactions on Computers, vol. 59, no. 1, pp. 29-41, 2010.
- A. Boukerche, J. M. Correa, A. Melo, and R. P. Jacobi, “A hardware accelerator for the fast retrieval of DIALIGN biological sequence alignments in linear space,” IEEE Transactions on Computers, vol. 59, no. 6, pp. 808-821, 2010.
- C. B. Olson, M. Kim, C. Clauson, B. Kogon, C. Ebeling, S. Hauck, and W. L. Ruzzo, “Hardware acceleration of short read mapping,” In Proceedings of the 20th IEEE Annual Int’l Symposium on Field-Programmable Custom Computing Machines, pp. 161-168, 2012.
- Y. Chen, B. Schmidt, and D. L. Maskell, “A hybrid short read mapping accelerator,” BMC Bioinformatics, 14:67, 2013.
- J. Arram, K. H. Tsoi, W. Luk, and P. Jiang, “Reconfigurable acceleration of short read mapping,” In Proceedings of the 21st IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 210-217, 2013.
- N.-F. Tzeng and A. Kongmunvattana, “Distributed shared memory systems with improved barrier synchronization and data transfer,” In Proceedings of the 11th ACM International Conference on Supercomputing (ICS), pp. 148-155, 1997.
- J. Cornwell and A. Kongmunvattana, “Advanced I/O techniques for efficient and highly available process crash recovery protocols,” GSTF Journal on Computing, vol. 1, no. 3, 2011.
Index Terms
Keywords