Abstract—The Next Generation Sequencing platform can
generate shorter reads, higher coverage, higher throughput
than the Sanger sequencing. These lowest cost technologies can
produce deeper coverage of most species, including mammals,
in few days at one run. The sequence data produced by one of
these instruments consist of millions or billions of sequence
reads ranging from 50 to 150nt in length. These short read must
be assembled de novo before further genome analysis can begin.
Unfortunately, genome assembly remains a difficult problem
challenged by many reasons, especially the short reads and the
complex repeats structure that longer than the reads. There are
many assembly algorithms and software recently, most of them
appear powerless by facing repeats, especially for the identical
ones and cannot get the unique assembly result with the
completely same input data. How to get the unique and stable
assembly result when repeats that longer than read contained
into the input data set is becoming a key issue. In this
perspective, we proposed a genome assembly method based on
dynamic overlap which can get unique result from the beginning
of randomly selected read and can resolve high similarity
repeats whose length is hundreds times of read length, more
importantly, we use single-end data but not paired-end
information to resolve high similarity repeats.
I. INTRODUCTION
VER the past twenty years, genome sequencing
technologies have made a great progress in many
aspects, such as speed, cost, coverage, etc. the
automated Sanger sequencing is regarded as the first-
generation genome sequencing technology which has the
ability to read through more than 1000 base pair
(1000-2000bp), and the later newer methods are referred to
the Next-Generation Sequencing(NGS) technologies.
Currently available commercial NGS platforms are Roche
454, Illumina/HiSeq, ABI/SOLiD, Helicos/Heliscope and
etc[1]. Next generation sequencing machines can now
sequence the whole human genome in few days, and this
capability has inspired a flood of new projects that are aiming
at sequencing large kinds of animals and plants[2][3]. NGS
can be characterized by highly parallel operation, higher
yield, simpler operation, shorter reads and much lower
cost[4].
So how to assembly a complete genome from these short
reads efficiently and accurately is becoming an urgent
problem. Assembly algorithms are greatly challenged by the
following several reasons.
• Complex repeat structure of genomes, especially for the
identical repeats which are longer than the reads[5].
This paper is supported by National Nature Science Fund
(Grant:61174163)
S Lian, X Dai is with School of Information Science and Technology, Sun
Yat-sen University, Guangzhou, China (phone: +86-020-39943331; e-mail:
shuai_lian@qq.com)
Complex repeats include Interspersed repeats, Tandem
repeats, Short interspersed nuclear elements(SINE),
Long interspersed nuclear elements(LINE).
• The fundamental limitations of the NGS technologies are
the NGS itself because the reads are much shorter, even
shorter than the smallest genome. Shorter reads deliver
less information per read so as to make assembling a
genome more difficult. Shorter reads require higher
coverage so as to satisfy the minimum overlap criteria,
higher coverage increase the complexity and intensity of
the computational issues related to the lager genome
data.
• Furthermore, sequencing error makes repeats resolution
more difficult. The existence of error makes assemblers
cannot correctly tell whether the difference is real
genome variation or caused by sequencing errors.
• Non-uniform coverage of the genomes in sequencing
process is another obstacle of whole genome assembly.
Low coverage can induce gaps in assembly, coverage
bias decreases the confidence of repeats resolution based
on coverage statistical tests[5].
• The computational of complexity of processing large
volume of data sets is also difficult to deal with, such as
human genome, Metagenomics. Computing overlaps
between two reads is most time consuming stage in
genome assembly. So for the large genome data,
assembly algorithms require the high-performance
computing platforms. Personal computer is almost
impossible for WGS assembly currently.
• And etc……..
Up to now, there are more than tens of genome assembly
algorithms. These NGS assemblers can be divided into three
categories, all are based on computing overlap or k-mers. The
overlap/Layout/Consensus(OLC) methods rely on the
overlap graphs. The de Bruijn Graphs(DBG) use K-mer graph
as another form of overlap. The Greedy graphs may combine
the OLC and DBG. Where SSAKE[6], SHARCGS[7],
ABySS[8], ALLPATHS[9], SOAPdenovo[10], Velvet[11]
are the typical ones. However, the efficiency and accuracy of
these currently assembly algorithms are different from each
other[12] due to many reasons.
Among these assemblies, most of them cannot deal well
with repeats longer than the reads, even for the high similarity
repeats with variations, furthermore, the assembling results
are not stable especially confounding identical repeats and
high similarity repeats. In this perspective, we proposed a
new genome assembly method based on dynamic overlap
called DOAssembler(Dynamic Overlap Assembly).
DOAssembler can resolve high similarity repeats up to 99%
similarity with read length 100bp and get the unique
assembly result from different beginning reads by using
A New Genome Assembly Method Based On Dynamic Overlap
Shuaibin Lian and Xianhua Dai
O
Third International Conference on Information Science and Technology
March 23-25, 2013; Yangzhou, Jiangsu, China
978-1-4673-2764-0/13/$31.00 ©2013 IEEE
1
资源评论
