Home // IMMM 2012, The Second International Conference on Advances in Information Mining and Management // View article

A Fast Short Read Alignment Algorithm Using Histogram-Based Features

Authors:
Qiu Chen
Koji Kotani
Feifei Lee
Tadahiro Ohmi

Keywords: Short read; Alignment; Fast search; Smith-Waterman; Histogram-based feature

Abstract:
Current new generation of DNA sequencers have had the ability to generate billions of short reads rapidly and inexpensively. How to solve fast and robust short read alignment problem become one of the most important challenges in bioinformatics research area. The current solutions for short-read alignment have limitations that alignment algorithms such as MAQ and Bowtie have few capabilities to align reads with insertions or deletions. In this paper, we propose an efficient hierarchical alignment algorithm to reduce it. For a given short read, first, a fast histogram search method is used to scan the reference sequence. Most of locations in reference sequence with low similarity will be excluded for latter searching. The Smith-Waterman alignment algorithm is then applied to each remainder location to search for exact matching. Experimental results show the proposed method combining histogram information and Smith-Waterman algorithm is a faster and accurate algorithm for short read alignment.

Pages: 114 to 117

Copyright: Copyright (c) IARIA, 2012

Publication date: October 21, 2012

Published in: conference

ISSN: 2326-9332

ISBN: 978-1-61208-227-1

Location: Venice, Italy

Dates: from October 21, 2012 to October 26, 2012