Solving the fully-connected 15-city TSP using probabilistic DNA computing

Fusheng Xiong, David Spetzler, Wayne Frasch

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Implementation of DNA computers has lagged behind the theoretical advances due to several technical limitations. These limitations include the amount of DNA required, the efficiency and accuracy of methods to generate and purify answers, and the lack of a reliable method to read the answer. Here we show how to perform calculations using a reasonable amount of DNA with greater efficiency and accuracy and a new readout method that was used to successfully solve a problem with 15 vertices and 210 edges, the largest problem ever solved with DNA. These advances will provide new opportunities for DNA computing to perform practical computations that utilize the massively parallel nature of DNA hybridization.

Original languageEnglish (US)
Pages (from-to)275-280
Number of pages6
JournalIntegrative Biology
Issue number3
StatePublished - 2009

ASJC Scopus subject areas

  • Biophysics
  • Biochemistry


Dive into the research topics of 'Solving the fully-connected 15-city TSP using probabilistic DNA computing'. Together they form a unique fingerprint.

Cite this