Biomedical Engineering Reference
In-Depth Information
CHAPTER 12
Assembling DNA Fragments with a
Distributed Genetic Algorithm
GABRIEL LUQUE, ENRIQUE ALBA, and SAMI KHURI
As more research centers embark on sequencing new genomes, the problem of DNA
fragment assembly for shotgun sequencing is growing in importance and complexity.
Accurate and fast assembly is a crucial part of any sequencing project and many
algorithms have been developed to tackle it. As the DNA fragment assembly problem
is NP-hard, exact solutions are very difficult to obtain. Various heuristics, including
genetic algorithms (GAs), were designed for solving the fragment assembly problem.
Although the sequential GA has given good results, it is unable to sequence very large
DNA molecules. In this work, we present a distributed genetic algorithm (dGA) that
surmounts the problem. We show how the dGA can tackle problem instances that are
77 kb long accurately.
12.1 INTRODUCTION
DNA fragment assembly is a technique that attempts to reconstruct the original DNA
sequence from a large number of fragments, each having several hundred base-pairs.
The DNA fragment assembly is needed because current technology, such as gel
electrophoresis, cannot directly and accurately sequence DNA molecules longer than
1000 bases. However, most genomes are much longer. For example, a human DNA
is about 3.2 billion nucleotides in length and cannot be read simultaneously.
The following technique was developed to deal with this limitation. First, the DNA
molecule is amplified, that is, many copies of the molecule are created. The molecules
are then cut at random sites to obtain fragments that are short enough to be sequenced
directly. The overlapping fragments are then assembled back into the original DNA
molecule. This strategy is called
shotgun sequencing
. Originally, the assembly of
Search WWH ::
Custom Search