Article

An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing

Author:

David HartAuthors Info & Claims

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 885 - 893

Published: 06 January 2002 Publication History

Get Access

Abstract

The final step for obtaining very accurate DNA sequence data is known as "finishing." Most steps of DNA sequencing are highly automated, but it is only recently that researchers have looked at automating the finishing step. Our perspective is to look at automated finishing as an optimization problem, with the goal to minimize lab costs.We give new algorithms for solving this problem. We look at a model of the problem for which previous researchers gave an O(n⁴) algorithm (where n is the length of the DNA measured in reads). We give an algorithm that runs in O(n^2⅓) worst case time. We then show that the algorithm runs in O(n) expected time, if we make an assumption, accepted by many molecular biologists, about randomness in the input data.

References

[1]

JGI and "bermuda-quality" sequence. Human Genome News, 9(3), 1998.

Google Scholar

[2]

International Human Genome Sequencing Consortium. Initial sequencing and analysis of the human genome. Nature, 409(6822):860-921, February 15 2001.

Google Scholar

[3]

Eva Czabarka, Goran Konjevod, Madhav V. Marathe, Alon G. Percus, and David C. Torney. Algorithms for optimizing production DNA sequencing. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 399-408. ACM-SIAM, 2000.

Digital Library

Google Scholar

[4]

David Gordon, Chris Abajian, and Phil Green. Consed: A graphical tool for sequence finishing. Genome Research, pages 195-202, March 1998.

Google Scholar

[5]

David Gordon, Cindy Desmarais, and Phil Green. Automated finishing with autofinish. Genome Research, pages 614-625, April 2001.

Google Scholar

[6]

Alon G. Percus and David C. Torney. Greedy algorithms for optimized DNA sequencing. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 955-956. ACM-SIAM, 1999.

Digital Library

Google Scholar

[7]

J. Craig Venter et al. The sequence of the human genome. Science, 291(5507):1304-1351, February 2001.

Google Scholar

An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

A parallel graph decomposition algorithm for DNA sequencing with nanopores

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 ~10⁵ will be available in large numbers and at high speed. We address the ...
Inferring relative proportions of DNA variants from sequencing electropherograms

Motivation: Determination of the relative copy number of single-nucleotide sequence variants (SNVs) within a DNA sample is a frequent experimental goal. Various methods can be applied to this problem, although hybridization-based approaches tend to ...
Anatomy of a hash-based long read sequence mapping algorithm for next generation DNA sequencing

Motivation: Recently, a number of programs have been proposed for mapping short reads to a reference genome. Many of them are heavily optimized for short-read mapping and hence are very efficient for shorter queries, but that makes them inefficient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

January 2002

1018 pages

ISBN:089871513X

Conference Chair:
David Eppstein

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2002

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
283
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Recommendations

A parallel graph decomposition algorithm for DNA sequencing with nanopores

Inferring relative proportions of DNA variants from sequencing electropherograms

Anatomy of a hash-based long read sequence mapping algorithm for next generation DNA sequencing