Fragment assembly through minimal forbidden words
Antonio Restivo, Filippo Mignosi, Marinella Sciortino, Gabriele Fici, Gabriele Fici, Filippo Mignosi, Antonio Restivo, Marinella Sciortino · 2004
We give a linear-time algorithm to reconstruct a nite word w over a nite alphabet A of constant size starting from a nite set of fac- tors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in pre- vious papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.