Abstract—Development of DNA sequence comparison technique is an active research activity in computational biology application. Commonly techniques studied are dynamic programming and heuristic algorithms. Exhaustive dynamic programming algorithm produces optimal result but requires longer time and bigger space. Heuristic algorithm gives approximate results with much faster processing. We have developed a new model that improves the speed of large scale DNA sequence similarity search and at the same time the best possible alignment result is retained. The model is known as a guided dynamic programming approach for DNA sequence similarity search (FRA-Search). Two approaches are used to complete the FRA-Search model: an automaton based exact string matching algorithm is employed to skip irrelevant database sequences from being computed for dynamic programming alignment processing and; the rough sets theory has been employed to classify and reduct the dataset. This paper discusses the parallel model for FRA-Search application. The parallel FRA-Search model is implemented on PC-based cluster system. It is developed on a single program multiple data (SPMD) architecture and MPJ Express software is used as a communication interface protocol between processors.

Index Terms—DNA sequence comparison, dynamic programming algorithm, SPMD architecture, parallel computing, MPJ Express.

A. R. M. Nordin is with the Faculty of Informatics, Universiti Darul Iman Malaysia, KUSZA Campus, 21300 K Terengganu, Malaysia. (Phone:+6096653300; Fax: +6096673412)
M. S. M. Yazid and A. Aziz are with the Faculty of Science and Technology, Universiti Malaysia Terengganu, 21030 K Terengganu,Malaysia.
M. T. A. Osman is with the Kuliyyah of Information Technology and Communication, International Islamic University of Malaysia, 50728 KualaLumpur, Malaysia.

Cite: A. R. M. Nordin, M. S. M. Yazid, A. Aziz and M. T. A. Osman, "Parallel Guided Dynamic Programming Approach for DNA Sequence Similarity Search," International Journal of Computer and Electrical Engineering vol. 1, no. 4, pp. 402-409, 2009.