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 9, 5 Issues, 2014


Download PDF Flyer




Current Bioinformatics

Aims & ScopeAbstracted/Indexed in

Ranking and Category:
  • 20th of 52 in Mathematical & Computational Biology

Submit Abstracts Online Submit Manuscripts Online

Editor-in-Chief:
Alessandro Giuliani
Istituto Superiore di Sanitá (Italian NIH) Environment and Health Dept
Roma
Italy


View Full Editorial Board

Subscribe Purchase Articles Order Reprints

Current: 1.726
5 - Year: 1.577

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

Affiliation: Dept of Computer Engineering Silla University, Busan Korea.

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 design a fuzzy logic system to control the gap cost dynamically to improve the quality of the alignment. In 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 alignment quality is also improved by our fuzzy inference system.


Purchase Online Rights and Permissions

  
  



Article Details

Volume: 9
First Page: 1
Page Count: 1
DOI: 10.2174/1574893609666140523000227
Advertisement

Related Journals




Webmaster Contact: urooj@benthamscience.org Copyright © 2014 Bentham Science