Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms

Kazuo Iwama, Junichi Teruyama, Shuntaro Tsuyama

The problem called "String reconstruction from substrings" is a mathematical model of sequencing by hybridization that plays an important role in DNA sequencing. In this problem, w…