{"id":287,"date":"2007-11-04T16:50:24","date_gmt":"2007-11-04T20:50:24","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=287"},"modified":"2007-11-04T16:50:24","modified_gmt":"2007-11-04T20:50:24","slug":"deoxyribononapproximability","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=287","title":{"rendered":"Deoxyribononapproximability"},"content":{"rendered":"

[Updates]<\/a><\/p>\n

Alright, here’s a problem for all you bioinformatistas and inapproximabistas out there, which was inspired by this post of Eliezer Yudkowsky<\/a> at Overcoming Bias<\/a> (see also the comments there).<\/p>\n

Let a DNA sequence be an element of {A,C,G,T}*, and suppose we’re allowed the following primitive operations: (1) insert a base pair anywhere we want, (2) delete any substring, (3) reverse any substring, and (4) copy any substring into any other part of the string. Then given a DNA sequence S, how hard is it to estimate the minimum number of operations needed to produce S starting from the empty string?<\/p>\n

Closely related is the following problem: by starting from the empty string and applying o(n) operations, can we produce a “pseudorandom DNA sequence” of length n — that is, a sequence that can’t be distinguished in polynomial time from a uniform random one?<\/p>\n

(Note 1:<\/em> For both problems, we might also want to stipulate that every intermediate sequence should have size at most polynomial in n. Or better yet, maybe one can prove that such an assumption is without loss of generality.)<\/font><\/p>\n

(Note 2:<\/em> I’m also very interested in what happens if we disallow the powerful operation of reversal.)<\/font><\/p>\n

For all I know, these problems might have trivial (or at any rate, known) answers; I just came up with them and haven’t thought them through.<\/p>\n

What the problems are really<\/em> getting at is this: is the “effective number of bits” in your genome (that is, the number of bits from a polynomial-time algorithm’s perspective) limited by how many ancestors you’ve had since life on Earth began? Or can it be vastly greater?<\/p>\n

<\/a>Update (11\/4):<\/font><\/strong> Rereading the last few paragraphs of Eliezer’s post, I see that he actually argues for his central claim — that the human genome can’t contain more than 25MB of “meaningful DNA” — on different (and much stronger) grounds than I thought! My apologies for not reading more carefully.<\/p>\n

In particular, the argument has nothing to do with the number of generations since the dawn of time, and instead deals with the maximum number of DNA bases that can be simultaneously protected, in steady state<\/em>, against copying errors. According to Eliezer, copying a DNA sequence involves a ~10-8<\/sup> probability of error per base pair, which — because only O(1) errors per generation can be corrected by natural selection — yields an upper bound of ~108<\/sup> on the number of “meaningful” base pairs in any given genome.<\/p>\n

However, while this argument is much better than my straw-man based on the number of generations, there’s still an interesting loophole. Even with a 10-8<\/sup> chance of copying errors, one could imagine a genome reliably encoding far more than 108<\/sup> bits (in fact, arbitrarily many bits) by using an error-correcting code. I’m not talking about the “local” error-correction mechanisms that we know DNA has, but about something more global — by which, say, copying errors in any small set of genes could be completely compensated by other genes. The interesting question is whether natural selection could read the syndrome of such a code, and then correct it, using O(1) randomly-chosen insertions, deletions, transpositions, and reversals. I admit that this seems unlikely, and that even if it’s possible in principle, it’s probably irrelevant to real biology. For apparently there are examples where changing even a single base pair leads to horrible mutations. And on top of that, we can’t have the error-correcting code be too<\/em> good, since otherwise we’ll suppress beneficial mutations!<\/p>\n

Incidentally, Eliezer’s argument makes the falsifiable prediction that we shouldn’t find any<\/em> organism, anywhere<\/em> in nature, with more than 25MB of functional DNA. Does anyone know of a candidate counterexample? (I know there are organisms with far more than humans’ 3 billion base pairs, but I have no idea how many of the base pairs are functional.)<\/p>\n

Lastly, in spite of everything above, I’d still like a solution to my “pseudorandom DNA sequence” problem. For if<\/em> the answer were negative — if given any DNA sequence, one could efficiently reconstruct a nearly-optimal sequence of insertions, transpositions, etc. producing it — then even my original straw-man misconstrual of Eliezer’s argument could put up a decent fight!<\/p>\n

Update (11\/5):<\/font><\/strong> Piotr Indyk pointed me to a paper<\/a> by Erg\u00fcn, Muthukrishnan, and Sahinalp from FSTTCS’2003, which basically solves my problem in the special case of no reversals. It turns out that you can estimate the number of insert, delete, and copy operations needed to produce a given DNA sequence to within a factor of 4, by just applying Lempel-Ziv compression to the sequence. Thanks, Piotr!<\/p>\n

Another Update (11\/5):<\/font><\/strong> Andy Drucker has pointed out that, in the case where reversals are<\/em> allowed, we can approximate the number of insert, delete, copy, and reverse operations needed to produce a given DNA sequence to within a factor of 16, by combining the Lempel-Ziv approach of Erg\u00fcn et al. with a clever trick: maintain both the sequence and its reversal at all times! Interestingly, though, this trick doesn’t<\/em> seem to work for transforming one sequence into another (a more general problem than I asked about, and the one considered by Erg\u00fcn et al).<\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

[Updates] Alright, here’s a problem for all you bioinformatistas and inapproximabistas out there, which was inspired by this post of Eliezer Yudkowsky at Overcoming Bias (see also the comments there). Let a DNA sequence be an element of {A,C,G,T}*, and suppose we’re allowed the following primitive operations: (1) insert a base pair anywhere we want, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5,30],"tags":[],"class_list":["post-287","post","type-post","status-publish","format-standard","hentry","category-complexity","category-mirrored-on-csail-blog"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/287","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=287"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/287\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}