Fast DNA Sequence Alignment Algorithm Based on Quality Score Using Improved Dynamic Programming and Fuzzy Gap Cost Control

ISSN: 2212-392X (Online)
ISSN: 1574-8936 (Print)

Volume 12, 6 Issues, 2017

Download PDF Flyer

Current Bioinformatics

This journal supports open access

Aims & ScopeAbstracted/Indexed in

Submit Abstracts Online Submit Manuscripts Online

Yi-Ping Phoebe Chen
Department of Computer Science and Information Technology
La Trobe University

View Full Editorial Board

Subscribe Purchase Articles Order Reprints

Current: 0.77
5 - Year: 0.93

Fast DNA Sequence Alignment Algorithm Based on Quality Score Using Improved Dynamic Programming and Fuzzy Gap Cost Control

Current Bioinformatics, 9(5): 540-547.

Author(s): Kwang Baek Kim, Hyun Jun Park and Doo Heon Song.

Affiliation: Department of Computer Engineering, Silla University, 140 Baegyang-Daero (Blvd) 700 Beon-Gil (Rd), Sasang-Gu, 617-736, Busan, Korea.


A sequence alignment algorithm is a basic building block for protein analysis and nucleic acid analysis in bioinformatics. Such alignment represents the similarities and differences of two or more compared sequences. Thus, there have been many algorithms and tools studied and developed. In this paper, we focus on the PHRED based sequence alignment algorithm using Needleman-Wunsch dynamic programming. Although it is well known and proven to be reliable to some extent, it suffers from the heavy computation of producing scoring matrix based on dynamic programming whose time complexity is O(mn). We propose a method applying quadrant method in that process to reduce the computational loads. Also, PHRED based algorithms suffer from the environment when low quality bases are frequently in tips of DNA fragments. Thus, we designed a fuzzy logic system to control the gap cost dynamically to improve the quality of the alignment. In the experiment using real genome data from NCBI (National Center for Biotechnology Information), we verify that the proposed method reduces the computational loads by half in producing scoring matrix and thus the alignment quality is also improved by our fuzzy inference system.


DNA sequence alignment, dynamic programming, fuzzy inference system, gap cost, quadrant, quality score.

Purchase Online Order Reprints Order Eprints Rights and Permissions

Article Details

Volume: 9
Issue Number: 5
First Page: 540
Last Page: 547
Page Count: 8
DOI: 10.2174/1574893609666140523000227
Price: $58
Global Biotechnology Congress 2017Drug Discovery and Therapy World Congress 2017

Related Journals

Related eBooks

Webmaster Contact: Copyright © 2017 Bentham Science