Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Copies of shredded text are needed to get 99.9% reconstruction of mutated text?

  1. Aug 5, 2011 #1


    User Avatar
    Gold Member

    This is a question posed by NASA astrobiologist Chris McKay (who wants to put life together back from its pieces), who really wants an answer to this question since it could lead us to reconstruct ancient genomes that are billions of years old (but mutated through years of internal radioactivity)

    - A text of length N composed of an alphabet of m distinct units (eg Hamlet has 29551 words and 60 distinct units - 52 letters, space, plus 7 punctuation marks)

    - Shred the text in pieces of average length X

    - How many copies C of the shredded text are needed to give 99.9% reconstruction?
  2. jcsd
  3. Aug 5, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't think this is a well defined mathematical problem unless you have information about how we are can recognize that two fragments of text go next to each other. For example does "invited for a" go with "a little drink" or "a necktie party"?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook