Xu Li; Zhenzhou Ji

International Journal of Engineering and Manufacturing (IJEM)

IJEM Vol. 1, No. 4, 29 Aug. 2011

Cover page and Table of Contents: PDF (size: 212KB)

Efficient Parallel Design for Edit distance algorithm in DNA Sequence Alignment

Full Text (PDF, 212KB), PP.32-38

Views: 0 Downloads: 0

Author(s)

Xu Li ¹ Zhenzhou Ji ¹

1. Department of Computer Science and Engineering, Harbin Institute of Technology, 150001 Harbin, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijem.2011.04.05

Received: 4 May 2011 / Revised: 14 Jun. 2011 / Accepted: 21 Jul. 2011 / Published: 29 Aug. 2011

Index Terms

Bioinformatics, sequence alignment, Needleman-Wunsch, Edit Distance, parallel design

Abstract

The focus of Bioinformatics research is usually on two aspects—genomics and proteomics, specifically, it’s starting from nucleic acid and protein sequences, analyzing the structural and functional biological information expressed in the sequences. Biological sequence alignment is one of the common problems, the Needleman-Wunsch algorithm based on dynamic programming is the most basic algorithm, and Edit Distance(Levenshtein Distance) algorithm is also widely used in DNA sequence alignment. Nowadays, there are large amount of improvements on the Needleman-Wunsch algorithm, while few on Edit Distance algorithm, so this paper focuses on revealing the effects of parallel design on optimizing the Edit Distance algorithm, and it also compares the two algorithms’ different significances in DNA sequence alignment objectively.

Cite This Paper

Xu Li,Zhenzhou Ji,"Efficient Parallel Design for Edit distance algorithm in DNA Sequence Alignment", IJEM, vol.1, no.4, pp.32-38, 2011. DOI: 10.5815/ijem.2011.04.05

Reference

[1]Zhongneng Xu, "Bioinformatics" ,Tsinghua University Press, Sep 2008,pp.134-137,150-164( in Chinese).
[2]Yangde Zhang, "Bioinformatics", Science Press, Jan 2009(in Chinese).
[3]T.K Attwood, D.J Parry-Smith, "Introduction to Bioinformatics ",Peking University Press, Apr 2002(in Chinese).
[4]T.H Cormen, "Introduction to Algorithms", China Machine Press, Jan 2008,pp.192-221.
[5]Guolinag Chen, "Design and Analysis of Parallel Algorithm," Higher Education Press, Aug 2009,pp.314-320(in Chinese).
[6]N.C Jones, P.A Pevzner, "An Introduction to Bioinformatics Algorithms" ,Chemical Industry Press, Jul 2007,pp.118-146(in Chinese).
[7]Lilan Tu, "Biological Sequence Alignment Based on Fast Walsh Transform", Hua zhong University of Science and Technology, Wuhan, 430074, P.R.China, Apr 2004,pp17-21(in Chinese).
[8]Kai Huang, Zhiwei Xu, "Scalable Parallel Computing Technology, Architecture, Programming", China Machine Press, May 2000, pp.8-18(inChinese).