Parallel Algorithms for Bioinformatics - Parallel Computing for Bioinformatics and Computational Biology - page 523

Molecule traversing the nanopore

n-type silicon
p-type silicon Metal contacts

SiO 2

SiO 2

Image
charges

Silicon wafer

Figure 21.8 A cross-section of the silicon-based nanosequencer [8]. Field effect transistors
are fabricated integrally with the nanopore. A single-stranded DNA molecule translocating
the nanopore induces image charges in the the silicon that are amplified and transmitted to a
computer. Differences in the dipole moments of the bases (A, C, T, or G) allow discrimination
between these bases [4].

proposals for discriminating between the bases (i.e., C, T, A, or G). In the silicon-
based nanosequencer proposed by Sauer and Van Zeghbroeck [8], bases are detected
by sensing the charge on the atoms that pass through, using field-effect transistors
embedded in the walls of the pore (Fig. 21.8).
A number of factors complicate the process of reassembling the target DNA from
the reads provided by a nanosequencer.

1. It is unlikely that the entire DNA of an organism could pass through (or trans-
locate) a nanopore without breaking. It is expected that reads will be of 10 5
bases in length.
2. The direction of translocation of a specific piece of ssDNA cannot be known.
3. The complementarity of a piece cannot be known.
4. There may be errors of biological or electrical origin in the sensed information.

It is possible to reconstruct the entire DNA of an organism, even under the condi-
tions enumerated earlier. In [10] we demonstrate how a variant of the Eulerian path
technique can reconstruct the entire 816394-base sequence of Mycoplasma pneumo-
niae from erroneous randomly sized reads, provided multiple DNA strands are input
to the sequencer.
The basic approach is to break all reads into k -mers and then create a histogram
of mer frequencies. A threshold frequency f t is then chosen to reject infrequently
occurring erroneous mers and create a deBruijn graph from the remaining. If the
resulting graph can be decomposed into exactly four disjoint paths, the reconstruction
is a success. If not, the process is repeated with a different k and f t . A 3D histogram
of mer frequencies for a range of f and k is shown in Figure 21.9.
Of immediate interest to us is the process of creating amer frequency histogramat a
fixed value of k , which would correspond to a slice through the surface of Figure 21.9.