2-AIN-505, 2-AIN-251: Seminár z bioinformatiky (1) a (3)
Zima 2014
Abstrakt

Gene Myers. Efficient Local Alignment Discovery amongst Noisy Long Reads. In WABI 2014, pp. 52-67, 2014.

Download preprint: not available

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX

Abstract:

Long read sequencers portend the possibility of producing reference 
quality genomes not only because the reads are long, but also because 
sequencing errors and read sampling are almost perfectly random. However, 
the error rates are as high as 15%, necessitating an efficient algorithm 
for finding local alignments between reads at a 30% difference rate, a 
level that current algorithm designs cannot handle or handle 
inefficiently. In this paper we present a very efficient yet highly 
sensitive, threaded filter, based on a novel sort and merge paradigm, that 
proposes seed points between pairs of reads that are likely to have a 
significant local alignment passing through them. We also present a linear 
expected-time heuristic based on the classic O(nd) difference algorithm 
[1] that finds a local alignment passing through a seed point that is 
exceedingly sensitive, failing but once every billion base pairs. These 
two results have been combined into a software program we call DALIGN that 
realizes the fastest program to date for finding overlaps and local 
alignments in very noisy long read DNA sequencing data sets and is thus a 
prelude to de novo long read assembly.