Voit muuntaa minkä tahansa merkkijonon tiivistefunktion "kanoniseksi" DNA-merkkijonon hash-funktioksi.

Annetaan DNA-merkkijono $ s $, olkoon $ \ overline {s} $ sen Watson-Crick-käänteinen täydennys . Oletetaan, että $ h: \ Sigma ^ * \ to \ mathbb {Z} $ on mielivaltainen merkkijonon tiivistefunktio. Voit määrittää $$ \ tilde {h} (s) \ triangleq \ min \ {h (s), h (\ overline {s}) \} $$ Sitten mille tahansa DNA-merkkijonolle $ s $$$ \ tilde {h } (s) = \ tilde {h} (\ overline {s}) = \ tilde {h} ({\ rm kanoninen} (s | h)) $$

PS: On enemmän kuin yksi tapa määritellä "kanoninen" hajautusfunktio. Olkoon esimerkiksi $ h_0 (\ cdot) $ 2-bittinen koodauksen hajautusfunktio. Kun otetaan huomioon mikä tahansa kokonaisluku -hajautusfunktio $ g (\ cdot) $, voimme määritellä: $$ h '(s) \ triangleq g \ big [\ min \ {h_0 (s), h_0 (\ overline {s}) \} \ iso] $$ Sitten meillä on vielä $$ h '(s) = h' (\ overline {s}) $$ Voit myös korvata $ \ min \ {\} $ XOR: lla tai plus: lla saada uusia määritelmiä.

Haluat kuitenkin.

Yksi tapa tehdä tämä on luoda sekä eteen- että taaksepäin täydentävät kilometrit, ja valitse sitten leksikografisesti pienin kmer tallennusavaimelle. Syvemmälle syventyminen edellyttää keskustelua esimerkiksi alla olevan taulukon koosta, avainten odotetusta jakautumisesta koko matriisiin ja siitä, minkä tyyppinen avainklusterointi on toivottavaa / ei-toivottua. Sillä, mitä todella tehdään, ei ole väliä, kunhan on olemassa deterministinen algoritmi, jota voidaan soveltaa kaikkiin mahdollisiin jaksoihin.

Useimpien nykyaikaisten kielten hienoa on, että heillä on jo oma hash-toteutukset, jotka yhdistävät avaimet arvoihin, jotka toimivat hyvin pikakokeissa: C ++: lla on järjestämätön kartta, perlillä on hasheja, pythonilla on sanakirjoja ja R: llä on nimiä.

Tekstimerkkijonoksi lukuiksi muuntavan asian varsinainen paljas metalli on monimutkainen, varsinkin jos haluat koodin olevan salattu ja hajautusryhmällä on pääsynopeus, joka on hyvin lähellä aikaa, joka kuluu yhden arvon noutamiseen muistista. Hyödyllinen lähtökohta tämän syvempään tutkimiseen voi olla Wikipedia-sivu Java hashcode -toiminnossa.