PDA

View Full Version : Copies of shredded text are needed to get 99.9% reconstruction of mutated text?


Simfish
Aug5-11, 03:46 PM
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?

Stephen Tashi
Aug5-11, 04:04 PM
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"?