Kodningsteoretiska tillvägagångssätt för nukleinsyradesign

DNA-kodkonstruktion hänvisar till tillämpningen av kodningsteori för design av nukleinsyrasystem för området DNA-baserad beräkning .

Introduktion

DNA- sekvenser uppträder i form av dubbla helixar i levande celler , där en DNA-sträng hybridiseras till sin komplementära sträng genom en serie vätebindningar . För syftet med denna post kommer vi att fokusera på endast oligonukleotider . DNA-beräkning innebär att tillåta syntetiska oligonukleotidsträngar att hybridisera på ett sådant sätt att de kan utföra beräkning . DNA-beräkning kräver att självmontering av oligonukleotidsträngarna sker på ett sådant sätt att hybridisering bör ske på ett sätt som är förenligt med beräkningsmålen.

Området för DNA-beräkning etablerades i Leonard M. Adelmans nyskapande artikel. Hans arbete är betydelsefullt av flera skäl:

Den visar hur man skulle kunna använda den mycket parallella karaktären hos beräkningar som utförs av DNA för att lösa problem som är svåra eller nästan omöjliga att lösa med de traditionella metoderna.
Det är ett exempel på beräkning på molekylär nivå, på linje med nanoberäkning , och detta är potentiellt en stor fördel när det gäller informationstätheten på lagringsmedia, som aldrig kan nås av halvledarindustrin.
Den visar unika aspekter av DNA som datastruktur.

Denna förmåga för massivt parallell beräkning i DNA-beräkningar kan utnyttjas för att lösa många beräkningsproblem i enormt stor skala, såsom cellbaserade beräkningssystem för cancerdiagnostik och behandling, och lagringsmedia med ultrahög densitet.

Detta urval av kodord (sekvenser av DNA-oligonukleotider) är ett stort hinder i sig på grund av fenomenet sekundär strukturbildning (där DNA-strängar tenderar att vikas på sig själva under hybridisering och därmed gör sig oanvändbara i ytterligare beräkningar. Detta är också känt som självhybridisering). Nussinov-Jacobson-algoritmen används för att förutsäga sekundära strukturer och även för att identifiera vissa designkriterier som minskar möjligheten till sekundär strukturbildning i ett kodord. I huvudsak visar denna algoritm hur närvaron av en cyklisk struktur i en DNA-kod minskar komplexiteten i problemet med att testa kodorden för sekundära strukturer.

Nya konstruktioner av sådana koder inkluderar användning av cykliska reversibla utökade Goppa-koder , generaliserade Hadamard-matriser och ett binärt tillvägagångssätt. Innan vi dyker in i dessa konstruktioner ska vi återgå till viss grundläggande genetisk terminologi. Motivationen för de satser som presenteras i denna artikel är att de överensstämmer med Nussinov - Jacobson-algoritmen, i det att förekomsten av cyklisk struktur hjälper till att minska komplexiteten och därmed förhindrar sekundär strukturbildning. dvs dessa algoritmer uppfyller vissa eller alla designkraven för DNA-oligonukleotider vid tidpunkten för hybridisering (vilket är kärnan i DNA-beräkningsprocessen) och lider därför inte av problemen med självhybridisering.

Definitioner

En DNA-kod är helt enkelt en uppsättning sekvenser över alfabetet ${\mathcal {Q}}=\{{\mathit {A}},{\mathit {T} },{\mathit {C}},{\mathit {G}}\}$ .

Varje purinbas är Watson-Crick-komplementet av en unik pyrimidinbas (och vice versa) – adenin och tymin bildar ett komplementärt par, liksom guanin och cytosin . Denna sammankoppling kan beskrivas enligt följande – ${\bar {A}}=T,{\bar {T}}=A, {\bar {C}}=G,{\bar {G}}=C$ .

Sådan parning är kemiskt mycket stabil och stark. Men parning av felaktiga baser inträffar ibland på grund av biologiska mutationer .

Det mesta av fokus på DNA-kodning har varit att konstruera stora uppsättningar av DNA-kodord med föreskrivna minimiavståndsegenskaper. Låt oss för detta ändamål lägga grunden för att gå vidare.

Låt ${\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q }}_{n}$ vara ett ord med längden ${\mathit {n}}$ över alfabetet ${\mathcal {Q}}$ . För ${\displaystyle 1\leqslant i\leqslant j\leqslant n} kommer vi att$ ${\mathit {q}}_{[i,j ]}$ notationen för att beteckna underföljden ${\mathit {q}}_{i}{\mathit {q}}_{i+1}\dots {\mathit {q }}_{j}$ . Dessutom kommer sekvensen som erhålls genom att vända ${\mathit {q}}$ betecknas som ${\mathit {q}}^{R}$ . Watson -Crick-komplementet , eller det omvända komplementet till q , definieras som ${\mathit {q}}^{RC}={ \mathit {{\bar {q}}_{n}}}{\mathit {{\bar {q}}_{n-1}}}\dots {\mathit {{\bar {q}}_{ 1}}}$ , där ${\mathit {{\bar {q}}_{i}}}$ anger Watson-Crick-komplementets baspar av ${\mathit {q }}_{i}$ .

För alla par av längd- ${\mathit {n}}$ ord ${\mathit {p}}$ och ${\mathit {q}}$ över ${ \mathcal {Q}}$ , Hamming-avståndet ${\mathit {d}}_{H}({\mathit {p}},{\mathit {q}})$ är antalet positioner ${\mathit {i}}$ där ${\mathit {p}}_{i}\neq {\mathit {q}}_{i }$ . Definiera vidare omvänd-Hamming-avstånd som ${\mathit {d_{H}}}^{R}({\mathit {p}} ,{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{R})$ . På liknande sätt är omvänd komplement Hamming-avstånd $\displaystyle {\mathit {d}}_{H}^{RC}({\mathit { p}},{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{RC})}$ . (där $RC}$ displaystyle står för omvänt komplement

En annan viktig koddesignövervägande kopplad till processen för oligonukleotidhybridisering hänför sig till GC-innehållet i sekvenser i en DNA-kod. GC -innehållet , ${\displaystyle {\mathit {w}}_{GC}({\mathit {q}})} ,$ av en DNA-sekvens ${ \displaystyle {\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q}}_{n}} definieras$ som antalet index ${\mathit {i}}$ så att ${\mathit {q}}_{i}\in \{G,C\}$ . En DNA-kod där alla kodord har samma GC-innehåll, $w$ , kallas en konstant GC-innehållskod .

En generaliserad Hadamard-matris ${\displaystyle {\mathit {H}}\equiv {\mathit {H}}(n,\mathbb {C} _{m})} är$ en ${\mathit {n}}$ $\times$ ${\mathit {n}}$ kvadratisk matris med poster hämtade från mängden ${\mathit {m}}$ rötterna till enhet, ${\displaystyle \mathbb {C} _{m}=\{e^{-2\pi { \mathit {i}}{\mathit {l}}/{\mathit {m}}}\mid l=0,\dots ,m-1\}} , som uppfyller H H ∗ {\$ displaystyle ${ H}}{\mathit {H}}^{*}}$ = ${\mathit {n}}{\mathit {I}}$ . Här ${\mathit {I}}$ identitetsmatrisen av ordningen ${\mathit {n}}$ , medan * står för komplex-konjugering. Vi kommer bara att ägna oss åt fallet ${\mathit {m}}={\mathit {p}}$ för vissa primtal ${\mathit {p}}$ . Ett nödvändigt villkor för existensen av generaliserade Hadamard-matriser ${\displaystyle {\mathit {H}}({\mathit {n}},\mathbb {C} _{p})} är$ att ${p}|{n}$ . Exponentmatrisen , $E({\mathit {n}},\mathbb {Z} _{p})$ , av $\displaystyle {\mathit {H}}({\mathit {n}},\mathbb {C} _{p})} är$ { matrisen n $\displaystyle {\mathit {n}}\times {\mathit {n}}}$ med posterna i ${\mathit {Z}}_{p}=\{0,1,2,\dots ,{\mathit {p }}-1\}$ , erhålls genom att ersätta varje post $(e^{-2\pi {\mathit {i}}l/{\mathit {m} }})$ i ${\mathit {H}}({\mathit {n}},\mathbb {C} _{p})$ av exponenten ${ \mathit {l}}$ .

Elementen i Hadamard-exponentmatrisen ligger i Galois-fältet ${\text{GF}}(p)$ , och dess radvektorer utgör kodorden för vad som ska kallas en generaliserad Hadamard-kod.

Här ligger elementen i ${\mathit {E}}$ i Galois-fältet ${\text{GF}}(p)$ .

Per definition har en generaliserad Hadamard-matris ${\mathit {H}}$ i sin standardform bara 1 s i sin första rad och kolumn. Den $({\mathit {n}}-1)\times ({\mathit {n}}-1)$ kvadratmatrisen som bildas av de återstående posterna av $H$ kallas kärnan i ${\mathit {H}}$ , och motsvarande submatris till exponentmatrisen ${\mathit {E}}$ kallas konstruktionens kärna . Genom att utelämna den första kolumnen helt noll är cykliska generaliserade Hadamard-koder möjliga, vars kodord är radvektorerna för den punkterade matrisen.

Dessutom uppfyller raderna i en sådan exponentmatris följande två egenskaper: (i) i var och en av raderna som inte är noll i exponentmatrisen, visas varje element i $\mathbb {Z} _{p}$ en konstant antal, ${\displaystyle {\mathit {n}}/{\mathit {p}}} ,$ av gånger; och (ii) Hamming-avståndet mellan två valfria rader är ${\mathit {n}}({\mathit {p}}-1)/{\mathit {p}}$ .

Fastighet U

Låt ${\mathit {C_{p}}}=\left\{1,x,x^{2},\ldots , x^{p-1}\right\}$ är den cykliska gruppen som genereras av ${\mathit {x}}$ , där $x=\ exp(2\pi ij/p)$ är en komplex primitiv ${\displaystyle p}:$ e roten av enhet, och $p>2$ är ett fast primtal. Låt vidare ${\displaystyle {\mathit {A}}=(x^{a_{i}})} ,$ B $\displaystyle {\mathit {B}} =(x^{b_{i}})}$ betecknar godtyckliga vektorer över $\mathbb {C} _{p}$ som har längden ${\mathit {N}}= pt$ , där ${\mathit {t}}$ är ett positivt heltal. Definiera samlingen av skillnader mellan exponenter ${\mathit {Q}}=\{a_{i}-b_{i} \mod p:i=1,2,\ldots ,N\}$ , där ${\mathit {n_{q}}}$ är multipliciteten av element ${\mathit {q} }$ av ${\text{GF}}(p)$ som visas i ${\mathit {Q}}$ .

Vektor ${\mathit {Q}}$ sägs uppfylla egenskap U om och endast om varje element ${\mathit {q}}$ i ${\text{GF }}(p)$ visas i ${\mathit {Q}}$ exakt ${\mathit {t}}$ gånger ( ${\mathit {n_{q}}}=t,q=0,1,\ldots ,p-1$ )

Följande lemma är av grundläggande betydelse för att konstruera generaliserade Hadamard-koder.

Lemma. Ortogonalitet av vektorer över ${\mathit {C_{p}}}$ – För fasta primtal ${\mathit {p}}$ , godtyckliga vektorer ${\mathit {A }},{\mathit {B}}$ av längden ${\displaystyle {\mathit {N}}=pt} ,$ vars element är från ${\mathit {C_{p}}}$ , är ortogonala om vektorn ${\mathit {Q}}$ uppfyller egenskapen U , där ${\mathit {Q}}$ är samlingen av skillnader $\mod {\ mathit {p}}$ mellan Hadamard-exponenterna associerade med ${\mathit {A}},{\mathit {B}}$ .

M-sekvenser

Låt ${\mathit {V}}$ vara en godtycklig vektor med längden ${\mathit {N}}$ vars element finns i det finita fältet ${\text{GF }}(p)$ , där $p$ är ett primtal. Låt elementen i en vektor $V$ utgöra den första perioden i en oändlig sekvens $a(V)$ som är periodisk för perioden $N$ . Om $N$ är den minsta perioden för att skapa någon delsekvens, kallas sekvensen en M-sekvens, eller en maximal sekvens av minsta period som erhålls genom att cykliskt permutera $N$ element. Om varje gång elementen i $V$ permuteras godtyckligt för att ge $V^{*}$ , är sekvensen $a(V^{*})$ en M -sekvens, då kallas sekvensen $a(V)$ M-invariant . De satser som följer nuvarande förhållanden som säkerställer M-invarians . Tillsammans med en viss enhetlighetsegenskap hos polynomkoefficienter ger dessa villkor en enkel metod med vilken komplexa Hadamard-matriser med cyklisk kärna kan konstrueras.

Målet här är att hitta cyklisk matris ${\mathit {E}}={\mathit {E_{c}}}$ vars element finns i Galois-fältet ${\text {GF}}(p)$ och vars dimension är $N=p^{n}-1$ . Raderna i ${\mathit {E}}$ kommer att vara kodorden som inte är noll i en linjär cyklisk kod ${\displaystyle K} ,$ om och endast om det finns polynom $g(x)$ med koefficienter i ${\displaystyle \mathrm {GF} (p)} ,$ som är en riktig divisor av ${\mathit {x^{N}-1}}$ och vilket genererar $K$ . För att ha $N$ kodord som inte är noll, måste $g(x)$ vara av graden $Nn$ . Vidare, för att generera en cyklisk Hadamard-kärna, måste vektorn (av koefficienterna för) $g(x)$ när den används med den cykliska växlingsoperationen vara av period $N$ , och vektorskillnaden för två godtyckliga rader av ${\mathit {E}}$ (förstärkt med noll) måste uppfylla enhetlighetsvillkoret för Butson, tidigare kallad egenskap U . Ett nödvändigt villkor för $N$ -periodicitet är att ${\displaystyle x^{N}-1=g(x)h(x)} ,$ där $h(x)$ är monisk irreducerbar över. Tillvägagångssättet här är att ersätta det sista kravet med villkoret att koefficienterna för vektorn $[0,g(x)]$ är likformigt fördelade över ${\ text{GF}}(p)$ , dvs varje rest $0,1,\ldots ,p-1$ visas lika många gånger (Egenskap U). Ett bevis på att detta heuristiska tillvägagångssätt alltid ger en cyklisk kärna ges nedan.

Exempel på kodkonstruktion

Kodkonstruktion med hjälp av komplexa Hadamard-matriser

Konstruktionsalgoritm

Betrakta ett moniskt irreducerbart polynom $h(x)$ över ${\text{GF}}(p)$ av grad ${\mathit {n}}$ med en lämplig följeslagare $g(x)$ av grad $Nn$ så att $g(x)h( x)=x^{N}-1$ , där vektorn $[0,g(x)]$ uppfyller egenskapen U . Detta kräver bara en enkel datoralgoritm för lång division över ${\text{GF}}(p)$ . Eftersom $h(x)|x^{N}-1$ , idealet genererat av $g(x)\mod (x^{N }-1)$ är en cyklisk kod ${\mathit {K}}$ . Dessutom egenskap U att kodorden som inte är noll bildar en cyklisk matris, varje rad med period $N$ under cyklisk permutation, som fungerar som en cyklisk kärna för Hadamard-matrisen ${\displaystyle H(p$ . Som ett exempel, en cyklisk kärna för $H(3,9)$ resulterar från kompanjonerna $h(x)=x^{ 2}+x+2$ och $g(x)=x^{6}+2x^{5} +2x^{4}+2x^{2}+x+1$ . Koefficienterna för $g$ indikerar att $\{0,1,6\}$ är den relativa skillnadsmängden, $\mod 8$ .

Sats

Låt ${\mathit {p}}$ vara ett primtal och ${\displaystyle {\mathit {N}}+1={\mathit {pn}}} ,$ med ${\mathit {g}}(x)$ ett moniskt polynom av grad ${\mathit {N}}-{\mathit {n}}$ vars utökade vektor av koefficienter $C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c} }_{N-1}]$ är element i ${\text{GF}}(p)$ . Anta att följande villkor gäller:

vektor $C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\dots ,{ \mathit {c}}_{N-1}]$ uppfyller egenskapen U, och
${\displaystyle g(x)h(x)=x^{N}-1} ,$ där $h(x)$ är en monic irreducerbart polynom av grad $n$ .

Sedan finns det en p -är linjär cyklisk kod ${\bar {K}}$ av blockstorlek $N$ , så att den utökade koden ${\displaystyle K=$ är exponentmatrisen för Hadamard-matrisen $H(p,p_{n})=xK$ , med $x=e^{2\pi i/p}$ , där kärnan i $H$ är en cyklisk matris.

Bevis:

Observera först att $g(x)$ är monisk och dividerar $x^{N}-1$ med graden $Nn$ . Nu måste vi visa att matrisen $E_{c}$ vars rader är kodord som inte är noll utgör en cyklisk kärna för någon komplex Hadamard-matris $H$ .

Givet att ${\mathit {C}}$ uppfyller egenskapen U, ligger alla rester som inte är noll i ${\text{GF}}(p)$ i C . Genom att cykliskt permutera element i $C$ får vi den önskade exponentmatrisen ${E_{c}}$ där vi kan få varje kodord i ${E_{c}}$ av permutering av det första kodordet. (Detta beror på att sekvensen som erhålls genom att cykliskt permutera $C$ är M-invariant.)

Vi ser också att förstärkning av varje kodord i ${E_{c}}$ genom att lägga till ett inledande nollelement ger en vektor som uppfyller egenskapen U. Dessutom, eftersom koden är linjär, är $\ mod p$ vektorskillnaden mellan två godtyckliga kodord är också ett kodord och uppfyller således egenskapen U . Därför bildar radvektorerna för den utökade koden ${\mathit {K}}$ en Hadamard-exponent. Således ${\mathit {xK}}$ standardformen för någon komplex Hadamard-matris ${\mathit {H}}$ .

Av ovanstående egenskap ser vi alltså att kärnan i ${\mathit {E}}$ är en cirkulerande matris som består av alla $N={\mathit {p}} ^{k}-1$ cykliska skift av dess första rad. En sådan kärna kallas en cyklisk kärna där i varje element i $\mathbb {Z} _{p}$ visas i varje rad av ${\mathit {E}}$ exakt $(N+1)/p={\mathit {p}}^{k-1}$ gånger, och Hamming-avståndet mellan två valfria rader är exakt $(N+1)(p-1)/p=(p-1)p^{k-1}$ . De ${\mathit {N}}$ raderna i kärnan ${\mathit {E}}$ bildar en konstant sammansättningskod - en som består av ${\mathit {N}}$ cykliska skift av någon längd ${\mathit {N}}$ över mängden $\mathbb {Z} _{p}$ . Hamming-avståndet mellan två valfria kodord i $\mathbb {Z} _{p}$ är $(p-1){\mathit {p}}^{k -1}$ .

Följande kan härledas från satsen som förklarats ovan. (För mer detaljerad läsning hänvisas läsaren till uppsatsen av Heng och Cooke.) Låt ${\mathit {N}}={\mathit {p}}^{\mathit {k }}-1$ för ${p}$ primtal och ${k}\in \mathbb {Z} ^{+}$ . Låt $g(x)=c_{0}+c_{1}x+c_{2} x^{2}+\dots +c_{Nk}x^{Nk}$ vara ett moniskt polynom över $\mathbb {Z} _{p}$ , av graden N − k så att ${\mathit {g}}({\mathit {x}}){\mathit {h}}({\mathit {x}})={\mathit { x}}^{N}-1$ över $\mathbb {Z} _{p}$ , för vissa moniska irreducerbara polynom ${\mathit {h }}({\mathit {x}})\in \mathbb {Z} _{p}[{\mathit {x}}]$ . Antag att vektorn ${\displaystyle ({c}_{0},{c}_{1} ,\ldots ,{c}_{Nk},{c}_{N-k+1},\ldots ,{c}_{N-1})} , med c i = {\$ displaystyle ${ c}}_{i}=0}$ för (N − k) < i < N, har egenskapen att den innehåller varje element av $\mathbb {Z} _{p}$ samma antal gånger . Sedan, de ${\mathit {N}}$ cykliska skiftningarna av vektorn ${\displaystyle {\mathit {g}}=({\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1})} utgör kärnan i exponentmatrisen för$ någon Hadamard-matris .

DNA-koder med konstant GC-innehåll kan uppenbarligen konstrueras från konstant sammansättningskoder (En konstant sammansättningskod över ett k-ary alfabet har egenskapen att antalet förekomster av de k symbolerna i ett kodord är samma för varje kodord) över $\mathbb {Z} _{p}$ genom att mappa symbolerna för $\mathbb {Z} _{p}$ till symbolerna för DNA-alfabetet, ${\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}$ . Till exempel, med cyklisk konstant sammansättningskod med längden ${\mathit {3}}^{k}-1$ över $\mathbb {Z} _{3}$ garanteras av teorem som bevisats ovan och den resulterande egenskapen, och med hjälp av mappningen som tar $0$ till ${\displaystyle {\mathit {A}}} ,$ 1 $\displaystyle 1}$ till ${\mathit {T} }$ och $2$ till ${\mathit {G}}$ får vi en DNA-kod ${\mathcal {D}}$ med ${\ mathit {3}}^{k}-1$ och ett GC-innehåll på ${\mathit {3}}^{k-1}$ . Helt klart ${\mathit {d_{H}}}=2.{\mathit {3}}^{k-1}$ och faktiskt eftersom ${\ displaystyle {\mathit {\bar {G}}}={\mathit {C}}}$ och inget kodord i ${\mathcal {D}}$ innehåller ingen symbol ${\mathit {C} }$ , vi har också ${\mathit {d}}_{H}^{RC}({\mathcal {D}})\geq 3^{ k-1}$ . Detta sammanfattas i följande resultat.

Naturlig följd

För alla ${\mathit {k}}\in \mathbb {Z} ^{+}$ finns det DNA-koder $\mathbb {D}$ med ${\ displaystyle {3}^{k}-1}$ kodord med längden ${3}^{k}-1$ , konstant GC-innehåll ${3}^{k- 1}$ , ${\mathit {d}}_{H}^{RC}(\mathbb {D} )\geq {3}^{k- 1}$ och där varje kodord är en cyklisk förskjutning av ett fix generatorkodord ${\mathit {g}}$ .

Var och en av följande vektorer genererar en cyklisk kärna av en Hadamard-matris $H(p,p^{n})$ (där ${\mathit {N }}+1={\mathit {p^{n}}}$ och ${\mathit {n}}=3$ i det här exemplet):

$g^{(1)}=(22201221202001110211210200)$ ;

$g^{(2)}=(20212210222001012112011100)$ .

Där, ${g(x)}=a_{0}+a_{1}x+\dots +a_{n}x^{n }$ .

Således ser vi hur DNA-koder kan erhållas från sådana generatorer genom att mappa , $\displaystyle {0,1,2}}$ på ${A,T,G}$ . Själva valet av kartläggning spelar en stor roll i sekundära strukturbildningar i kodorden.

Vi ser att alla sådana mappningar ger koder med i huvudsak samma parametrar. Men själva valet av mappning har ett starkt inflytande på kodordens sekundära struktur. Till exempel erhölls det illustrerade kodordet från ${g^{(1)}}$ via mappningen $0-A;1-T;2-G$ , medan kodordet ${g^{(2)}}$ erhölls från samma generator ${g^{(1)}}$ via mappningen $0-G;1-T;2-A$ .

Kodkonstruktion via en binär mappning

Kanske är ett enklare tillvägagångssätt för att bygga/designa DNA-kodord genom att ha en binär mappning genom att se på designproblemet som att konstruera kodorden som binära koder. dvs mappa DNA-kodordets alfabet ${\mathcal {Q}}$ på uppsättningen av 2-bitars binära ord som visas: ${\mathit {A}}\to 00$ , ${\mathit {T}}\to 01$ , ${\mathit {C}}\to 10$ , ${\mathit {G}}\to 11$ .

Som vi kan se bestämmer den första biten av en binär bild tydligt vilket komplementärt par den tillhör.

Låt ${\mathit {q}}$ vara en DNA-sekvens. Sekvensen ${b(q)}$ som erhålls genom att tillämpa mappningen ovan på ${\mathit {q}}$ kallas den binära bilden av ${\mathit {q}}$ .

Låt nu $b(q)={\mathit {b}}_{0}{\mathit {b}}_{1}{ \mathit {b}}_{2}\dots {\mathit {b}}_{2n-1}$ .

Låt nu underföljden $e(q)={\mathit {b}}_{0}{\mathit {b}}_{2}\ prickar {\mathit {b}}_{2n-2}$ kallas den jämna följden av ${b(q)}$ , och $o(q)={\mathit {b}}_{1}{\mathit {b}}_{3}{\mathit {b}}_{5}\ldots {\mathit {b}}_{2n-1}$ kallas den udda underföljden av ${b(q)}$ .

Således, till exempel, för $q=ACGTCC$ , då, $b(q)=001011011010$ .

Då är $e(q)=011011$ och $o(q)=001100$ .

Låt oss definiera en jämn komponent som ${\mathcal {E}}({\mathcal {C}})=\{e(x):x \in {\mathcal {C}}\}$ , och en udda komponent som ${\mathcal {O}}({\mathcal {C} })=\{o(x):x\in {\mathcal {C}}\}$ .

Från detta val av binär mappning är GC-innehållet för DNA-sekvensen ${\mathit {q}}$ = Hamming-vikten av ${e(q)}$ .

Därför är en DNA-kod ${\mathcal {C}}$ ett konstant GC-innehållskodord om och endast om dess jämna komponent ${\mathcal {E}}({\mathcal { C}})$ är en kod med konstant vikt.

Låt ${\mathcal {B}}$ vara en binär kod som består av $M$ kodord med längden ${\mathit {n}}$ och minsta avstånd ${d_ {\min }}$ , så att ${\mathit {c}}\in {\mathcal {B}}$ antyder att ${\mathit {\bar {c} }}\in {\mathcal {B}}$ .

För ${\mathit {w}}>0$ , betrakta underkoden med konstant vikt ${\displaystyle {\mathcal {B_{\mathit {w}}}}=\{u\in {\mathcal {B}}:{\mathit {w_{H}}}(u)={\mathit {w}}\}} ,$ där ${w_{H}(\cdot )}$ anger Hamming-vikt. Välj ${\mathit {w}}>0$ så att ${\mathit {n}}\geq {\mathit {2w}}+\ lceil {\mathit {d_{\min }}}/2\rceil$ , och överväg en DNA-kod, ${\mathcal {C}}_{w}$ , med följande val för dess jämna och udda komponenter:

${\mathcal {E}}=\left\{a{\bar {b}}:a,b\in {\mathcal {B}} _{w}\right\}$ , ${\mathcal {O}}=\left\{ab^{RC }:a,b\in {\mathcal {B}},a<_{lex}b\right\}$ .

Där $<_{lex}$ betecknar lexikografisk ordning. a $a<_{lex}b$ i definitionen av ${\mathcal {O}}$ säkerställer att om $\displaystyle ab^{RC }\i {\mathcal {O}}}$ , sedan $ba^{RC}\notin {\mathcal {O}}$ , så att distinkta kodord i ${\mathcal {O}}$ kan inte vara omvända komplement till varandra.

Koden ${\mathcal {E}}_{w}$ har ${\left\vert {\mathcal {B}}_{w}\right\vert }^{2}$ kodord med längden $2n$ och konstant vikt $n$ .

Dessutom ${\mathit {d_{H}}}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})$ och ${\mathit {d_{H}}}^{R}({\mathcal {E}}_{w}\geq {\mathit {d_{\ min }}})$ (detta beror på att ${\mathcal {B}}_{w}$ är en delmängd av kodorden i ${\mathcal {B}}$ ).

Även ${\mathit {d_{H}}}(a{\bar {b}},d^{RC}c^{R})={\mathit {d_{H}}} (a,d^{RC})+{\mathit {d_{H}}}({\bar {b}},c^{R})={\mathit {d_{H}}}(a,d ^{RC})+{\mathit {d_{H}}}(c,b^{RC})$ .

Observera att $b$ och $d$ båda har vikten ${\mathit {w}}$ . Detta innebär att $b^{RC}$ och $d^{RC}$ har vikten ${\mathit {nw}}$ .

Och på grund av viktbegränsningen på ${\mathit {w}}$ måste vi ha för alla $a,b,c,d\in {\mathcal {B}}_{w}$ , $a{ \bar {b}},d^{RC}c^{R})\geq 2\lceil {\mathit {d_{\min }}}/2\rceil \geq {\mathit {d_{\min }} }}$ .

har koden ${\mathcal {O}}$ $M(M-1)/2$ kodord med längden $2n$ .

Av detta ser vi att ${\displaystyle {d_{H}}(({\mathcal {O}}))\geq {d_{\min }}} ($ eftersom komponenten kodord för ${\mathcal {(}}O)$ är hämtade från ${\displaystyle {\mathcal {B}}} )$ .

På liknande sätt, ${d_{H}^{RC}}(({\mathcal {O}}))\geq {d_{\min }}$ .

Därför DNA-koden

{\mathcal {C}}=\bigcup _{w=d_{\min }}^{w_{\max }}{\mathcal {C}}_ {w}

med ${\displaystyle {w_{\max }}=({n}-\lceil d_{\min }/2\rceil )/2} ,$ har ${\frac {1}{2}}M(M-1)\sum _{w=d_{\min }}^{w_{\max }}\left\vert {A_{w}}^ {2}\right\vert$ kodord med längden $2{\mathit {n}}$ , och uppfyller ${\mathit {d_{H}}}( {\mathcal {B}})\geq {\mathit {d_{\min }}}$ och ${\mathit {d_{H}}}^{RC} ({\mathcal {B}})\geq {\mathit {d_{\min }}}$ .

Från exemplen som listas ovan kan man undra vad som kan vara den framtida potentialen för DNA-baserade datorer?

Trots sin enorma potential är det högst osannolikt att denna metod kommer att implementeras i hemdatorer eller ens datorer på kontor, etc. på grund av den stora flexibiliteten och hastigheten samt kostnadsfaktorer som gynnar kiselchipbaserade enheter som används för datorerna idag.

En sådan metod skulle emellertid kunna användas i situationer där den enda tillgängliga metoden är denna och kräver den noggrannhet som är associerad med DNA-hybridiseringsmekanismen; applikationer som kräver att operationer utförs med en hög grad av tillförlitlighet.

För närvarande finns det flera mjukvarupaket, såsom Vienna-paketet, som kan förutsäga sekundära strukturbildningar i enkelsträngade DNA (dvs oligonukleotider) eller RNA-sekvenser.

Se även

externa länkar

Atri Rudras kurs vid The State University of New York, Buffalo