Generic placeholder image

Current Bioinformatics

Editor-in-Chief

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

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

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

Volume 9, Issue 5, 2014

Page: [540 - 547] Pages: 8

DOI: 10.2174/1574893609666140523000227

Price: $65

Abstract

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.

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


Rights & Permissions Print Cite
© 2024 Bentham Science Publishers | Privacy Policy