Skip Navigation



Bioinformatics Advance Access published online on November 11, 2004
Bioinformatics, doi:10.1093/bioinformatics/bti129
Bioinformatics © Oxford University Press 2004; all rights reserved
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow All Versions of this Article:
21/7/889    most recent
bti129v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bokhari, S. H.
Right arrow Articles by Sauer, J. R.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Bokhari, S. H.
Right arrow Articles by Sauer, J. R.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Received August 5, 2004
Revised October 2, 2004
Accepted October 25, 2004

Article

A parallel graph decomposition algorithm for DNA sequencing with nanopores

Shahid H. Bokhari 1* and Jon R. Sauer 2

1 Department of Electrical Engineering, UET, Lahore-54890, Pakistan
2 Eagle Research & Development, 1898 S. Flatiron Court, Suite 128, Boulder, Colorado, 80301

* To whom correspondence should be addressed.
Shahid H. Bokhari, E-mail: shb{at}acm.org


  Abstract

Motivation: With the potential availability of nanopore devices that can sense the bases of translocating single-stranded DNA (ssDNA), it is likely that ‘reads’ of length ~105 will be available in large numbers and at high speed. We address the problem of complete DNA sequencing using such reads.

We assume that ~102 copies of a DNA sequence are split into single strands that break into randomly sized pieces as they translocate the nanopore in arbitrary orientations. The nanopore senses and reports each individual base that passes through, but all information about orientation and complementarity of the ssDNA subsequences is lost. Random errors (both biological and transduction) in the reads create further complications.

Results: We have developed an algorithm that addresses these issues. It can be considered an extreme variation of the well-known Eulerian path approach. It searches over a space of de Bruijn graphs until it finds one in which (a) the impact of errors is eliminated and (b) both possible orientations of the two ssDNA sequences can be identified separately and unambiguously.

Our algorithm is able to correctly reconstruct real DNA sequences of the order of 106 bases (e.g. the bacterium Mycoplasma pneumoniae) from simulated erroneous reads on a modest workstation in about one hour. We describe, and give measured timings of, a parallel implementation of this algorithm on the Cray Multithreaded Architecture (MTA-2) supercomputer, whose architecture is ideally suited to this ‘unstructured’ problem. Our parallel implementation is crucial to the problem of rapidly sequencing long DNA sequences and also to the situation where multiple nanopores are used to obtain a high-bandwidth stream of reads.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Genome ResHome page
D. R. Zerbino and E. Birney
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs
Genome Res., May 1, 2008; 18(5): 821 - 829.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.