A Comparison of Computation Techniques for DNA Sequence Comparison

Download Full Text
Harshita G. Patil, Manish Narnaware
Published Date:
April 30, 2012
Volume 2, Issue 3
1 - 6

dynamic programming algorithms, fasta, sequences alignment, tiling
Harshita G. Patil, Manish Narnaware, "A Comparison of Computation Techniques for DNA Sequence Comparison". International Journal of Research in Computer Science, 2 (3): pp. 1-6, April 2012. doi:10.7815/ijorcs.23.2012.021 Other Formats


This Project shows a comparison survey done on DNA sequence comparison techniques. The various techniques implemented are sequential comparison, multithreading on a single computer and multithreading using parallel processing. This Project shows the issues involved in implementing a dynamic programming algorithm for biological sequence comparison on a general purpose parallel computing platform Tiling is an important technique for extraction of parallelism. Informally, tiling consists of partitioning the iteration space into several chunks of computation called tiles (blocks) such that sequential traversal of the tiles covers the entire iteration space. The idea behind tiling is to increase the granularity of computation and decrease the amount of communication incurred between processors. This makes tiling more suitable for distributed memory architectures where communication startup costs are very high and hence frequent communication is undesirable. Our work to develop sequence-comparison mechanism and software supports the identification of sequences of DNA.

  1. Sudha Gunturu*, Xiaolin Li*, and Laurence Tianruo Yang** “Load Scheduling Strategies for Parallel DNA Sequencing Applications” 11th IEEE International Conference on High Performance Computing and Communications 2009.
  2. Armin Gr¨oßlinger “Some Experiments on Tiling Loop Programs for Shared-Memory Multicore Architectures” Dagstuhl Seminar Proceedings 07361 Programming Models for Ubiquitous Parallelism 2008.
  3. Nasreddine Hireche, J.M. Pierre Langlois and Gabriela Nicolescu Département de Génie Informatique, École Polytechnique de Montréal ‘‘Survey of Biological High Performance Computing: Algorithms, Implementations and Outlook Research’’ IEEE CCECE/CCGEI, Ottawa, May 2006. doi:10.1109/CCECE.2006.277302
  4. Friman S´anchez, Esther Salam´ı, Alex Ramirez and Mateo Valero HiPEAC European Network of Excellence Universitat Polit`ecnica de Catalunya (UPC), Barcelona, Spain “Parallel Processing in Biological Sequence Comparison Using General Purpose Processors” 2005 IEEE. doi:10.1109/IISWC.2005.1526005
  5. Matteo Canella - Filippo Miglioli Universit`a di Ferrara (Italy) Alessandro Bogliolo Universit`a di Urbino (Italy) Enrico Petraglio - Eduardo Sanchez Ecole Polytechnique F´ed´erale de Lausanne EPFL-LSL,Lausanne (Switzerland)” Performing DNA Comparison on a Bio-Inspired Tissue of FPGAs” Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS’03) 2003 IEEE. doi:10.1109/IPDPS.2003.1213358
  6. N. F. Almeida Jr ,C. E. R. Alves, E. N. Caceres, S. W.Song ”Comparison of Genomes using High-Performance Parallel Computing” Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’03) 2003 IEEE. doi:10.1109/CAHPC.2003.1250332
  7. Fa Zhang, Xiang-Zhen Qiao and Zhi-Yong Liu Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, National Natural Science Foundation of China, Beijing, 100083”A Parallel Smith-Waterman Algorithm Based on Divide and Conquer” Proceedings of the Fifth International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP.02) 2002 IEEE. doi:10.1109/ICAPP.2002.1173568
  8. W.S Martins, J.B Del Cuvillo, F.J.Useche, K.B Theobald, G.R.Gao Department of Electrical and Computer Engineering University of Delaware, Newark DE19716, USA” A Multithreaded Parallel Implementation of a Dynamic Programming Algorithm for Sequence Comparison” Pacific Symposium on Biocomputing 6:311-322 (2001).
  9. Subhra Sundar Bandyopadhyay, Somnath Paul and Amit Konar Electronics and Telecommunication Department Jadavpur University, Kolkata, India “Improved Algorithms for DNA Sequence Alignment and Revision of Scoring.

    Sorry, there are no citation(s) for this manuscript yet.