{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:24:14Z","timestamp":1756311854480,"version":"3.32.0"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: With the potential availability of nanopore devices that can sense the bases of translocating single-stranded DNA (ssDNA), it is likely that \u2018reads\u2019 of length \u223c105 will be available in large numbers and at high speed. We address the problem of complete DNA sequencing using such reads.<\/jats:p><jats:p>We assume that \u223c102 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.<\/jats:p><jats:p>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.<\/jats:p><jats:p>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 1 h. 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 \u2018unstructured\u2019 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.<\/jats:p><jats:p>Contact: \u00a0shb@acm.org<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti129","type":"journal-article","created":{"date-parts":[[2004,11,12]],"date-time":"2004-11-12T01:14:59Z","timestamp":1100222099000},"page":"889-896","source":"Crossref","is-referenced-by-count":13,"title":["A parallel graph decomposition algorithm for DNA sequencing with nanopores"],"prefix":"10.1093","volume":"21","author":[{"given":"Shahid H.","family":"Bokhari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jon R.","family":"Sauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2004,11,11]]},"reference":[{"key":"2023013107283408600_B1","doi-asserted-by":"crossref","unstructured":"Alverson, R., Callahan, D., Cummings, D., Koblenz, B., Porterfield, A., Smith, B. 1990The Tera computer system. Proceedings of the Fourth International Conference on Supercomputing ACM Press, pp. 1\u20136","DOI":"10.1145\/255129.255132"},{"key":"2023013107283408600_B2","doi-asserted-by":"crossref","unstructured":"Alverson, G., Alverson, R., Callahan, D., Koblenz, B., Porterfield, A., Smith, B. 1992Exploiting heterogeneous parallelism on a multithreaded multiprocessor. Proceedings of the Sixth International Conference on Supercomputing ACM Press, pp. 188\u2013187","DOI":"10.1145\/143369.143408"},{"key":"2023013107283408600_B3","doi-asserted-by":"crossref","unstructured":"Bailey, J.A., Gu, Z., Clark, R.A., Reinert, K., Samonte, R.V., Schwartz, S., Adams, M.D., Myers, E.W., Li, P.W., Eichler, E. 2002Recent segmental duplications in the human genome. Science297945\u2013947","DOI":"10.1126\/science.1072047"},{"key":"2023013107283408600_B4","doi-asserted-by":"crossref","unstructured":"Bokhari, S.H., Glaser, M.A., Jordan, H.F., Lansac, Y., Sauer, J.R., Van Zeghbroeck, B. 2002Parallelizing a DNA simulation code for the Cray MTA-2. Proceedings of the IEEE Computer Society Bioinformatics Conference IEEE, pp. 291\u2013302","DOI":"10.1109\/CSB.2002.1039351"},{"key":"2023013107283408600_B5","doi-asserted-by":"crossref","unstructured":"Bokhari, S.H. and Sauer, J.R. 2004Sequence alignment on the Cray MTA-2. Concurrency Comput.16823\u2013839","DOI":"10.1002\/cpe.808"},{"key":"2023013107283408600_B6","doi-asserted-by":"crossref","unstructured":"Branton, D. and Meller, A. 2002Using nanopores to discriminate between single molecules of DNA. Structure and Dynamics of Confined Polymers , Dordrecht Kluwer Academic Publishers, pp. 17\u2013185","DOI":"10.1007\/978-94-010-0401-5_11"},{"key":"2023013107283408600_B7","doi-asserted-by":"crossref","unstructured":"Gusfield, D. Algorithms on Strings, Trees, and Sequences1997, Combridge Cambridge University Press","DOI":"10.1017\/CBO9780511574931"},{"key":"2023013107283408600_B8","doi-asserted-by":"crossref","unstructured":"Howorka, S., Cheley, S., Bayley, H. 2001Sequence-specific detection of individual DNA strands using engineered nanopores. Nature Biotechnol.19, pp. 636\u2013639","DOI":"10.1038\/90236"},{"key":"2023013107283408600_B9","unstructured":"Idury, R. and Waterman, M. 1995A new algorithm for DNA sequence assembly. J. Comput. Biol.2291\u2013306"},{"key":"2023013107283408600_B10","doi-asserted-by":"crossref","unstructured":"Kasianowicz, J.J., Brandin, E., Branton, D., Deamer, D.W. 1996Characterization of individual polynucleotide molecules using a membrane channel. Proc. Natl Acad. Sci. USA9313770\u201313773","DOI":"10.1073\/pnas.93.24.13770"},{"key":"2023013107283408600_B11","doi-asserted-by":"crossref","unstructured":"Li, J., Stein, D., McMullan, C., Branton, D., Aziz, M., Golovchenko, J. 2001Ion-beam sculpting at nanometre length scales. Nature412","DOI":"10.1038\/35084037"},{"key":"2023013107283408600_B12","doi-asserted-by":"crossref","unstructured":"Li, J., Gershow, M., Stein, D., Brandin, E., Golovchenko, J. 2003DNA molecules and configurations in a solid-state nanopore microscope. Nature Mater.2611\u2013615","DOI":"10.1038\/nmat965"},{"key":"2023013107283408600_B13","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A. Computational Molecular Biology\u2014An Algorithmic Approach2000, Cambridge, MA The MIT Press","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"2023013107283408600_B14","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S. 2001An Eulerian path approach to DNA fragment assembly. Proc. Natl Acad. Sci. USA98, pp. 8748\u20139753","DOI":"10.1073\/pnas.171285098"},{"key":"2023013107283408600_B15","unstructured":"Sauer, J. and Van Zeghbroeck, B. 2002Ultra-fast nucleic acid sequencing device and a method for making and using the same. US Patent No. 6,413,792"},{"key":"2023013107283408600_B16","doi-asserted-by":"crossref","unstructured":"Sauer-Budge, A.F., Nyarnwanda, J.A., Lubensky, D.K., Branton, D. 2003Unzipping kinetics of double-stranded DNA in a nanopore. Phys. Rev. Lett.9023801-1\u201323801-4","DOI":"10.1103\/PhysRevLett.90.238101"},{"key":"2023013107283408600_B17","doi-asserted-by":"crossref","unstructured":"Storm, A.J., Chen, J., Ling, X., Zandbergen, H., Dekker, C. 2003Fabrication of solid-state nanopores with single-nanometer precision. Nature Mater.2537\u2013540","DOI":"10.1038\/nmat941"},{"key":"2023013107283408600_B18","unstructured":"Storm, A.J., Storm, C., Chen, J., Zandbergen, H., Joanny, J.-F., Dekker, C. 2004Fast DNA translocation through a solid-state nanopore. Preprint: arXiv:q-bio. BM\/0404041"},{"key":"2023013107283408600_B19","unstructured":"Waterman, M.S. Introduction to Computational Biology1995, London Chapman and Hall"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/889\/48967280\/bioinformatics_21_7_889.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/889\/48967280\/bioinformatics_21_7_889.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T23:25:16Z","timestamp":1734650716000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/7\/889\/268998"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,11]]},"references-count":19,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2005,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti129","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2005,4,1]]},"published":{"date-parts":[[2004,11,11]]}}}