Reconstructing strings from substrings in rounds

Dimitris Margaritis; Steven S. Skiena

Reconstructing strings from substrings in rounds

Dimitris Margaritis
, Steven S. Skiena

Computer Science

Stony Brook University

Research output: Contribution to journal › Conference article › peer-review

50 Scopus citations

Abstract

We establish a variety of combinatorial bounds on the tradeoffs inherent in reconstructing strings using few rounds of a given number of substring queries per round. These results lead us to propose a new approach to sequencing by hybridization (SBH), which uses interaction to dramatically reduce the number of oligonucleotides used for de novo sequencing of large DNA fragments, while preserving the parallelism which is the primary advantage of SBH.

Original language	English
Pages (from-to)	613-620
Number of pages	8
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 1995
Event	Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA Duration: Oct 23 1995 → Oct 25 1995

Cite this

@article{bab137cc907d4f79939d10313d0e4ada,

title = "Reconstructing strings from substrings in rounds",

abstract = "We establish a variety of combinatorial bounds on the tradeoffs inherent in reconstructing strings using few rounds of a given number of substring queries per round. These results lead us to propose a new approach to sequencing by hybridization (SBH), which uses interaction to dramatically reduce the number of oligonucleotides used for de novo sequencing of large DNA fragments, while preserving the parallelism which is the primary advantage of SBH.",

author = "Dimitris Margaritis and Skiena, \{Steven S.\}",

year = "1995",

language = "English",

pages = "613--620",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science ; Conference date: 23-10-1995 Through 25-10-1995",

}

TY - JOUR

T1 - Reconstructing strings from substrings in rounds

AU - Margaritis, Dimitris

AU - Skiena, Steven S.

PY - 1995

Y1 - 1995

N2 - We establish a variety of combinatorial bounds on the tradeoffs inherent in reconstructing strings using few rounds of a given number of substring queries per round. These results lead us to propose a new approach to sequencing by hybridization (SBH), which uses interaction to dramatically reduce the number of oligonucleotides used for de novo sequencing of large DNA fragments, while preserving the parallelism which is the primary advantage of SBH.

AB - We establish a variety of combinatorial bounds on the tradeoffs inherent in reconstructing strings using few rounds of a given number of substring queries per round. These results lead us to propose a new approach to sequencing by hybridization (SBH), which uses interaction to dramatically reduce the number of oligonucleotides used for de novo sequencing of large DNA fragments, while preserving the parallelism which is the primary advantage of SBH.

UR - https://www.scopus.com/pages/publications/0029510898

M3 - Conference article

AN - SCOPUS:0029510898

SN - 0272-5428

SP - 613

EP - 620

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science

Y2 - 23 October 1995 through 25 October 1995

ER -

Reconstructing strings from substrings in rounds

Abstract

Other files and links

Fingerprint

Cite this