Enfoques de la teoría de la codificación para el diseño de ácidos nucleicos

La construcción del código de ADN se refiere a la aplicación de la teoría de codificación al diseño de sistemas de ácidos nucleicos para el campo de la computación basada en ADN .

Introducción

Se sabe que las secuencias de ADN aparecen en forma de dobles hélices en las células vivas , en las que una hebra de ADN se hibrida con su hebra complementaria a través de una serie de enlaces de hidrógeno . Para el propósito de esta entrada, nos centraremos únicamente en los oligonucleótidos . La computación del ADN implica permitir que las hebras de oligonucleótidos sintéticos se hibriden de tal manera que se puedan realizar los cálculos . La computación del ADN requiere que el autoensamblaje de las hebras de oligonucleótidos ocurra de tal manera que la hibridación se produzca de una manera compatible con los objetivos del cálculo.

El campo de la computación del ADN se estableció en el artículo seminal de Leonard M. Adelman. ^[1] Su trabajo es importante por varias razones:

• Muestra cómo se podría utilizar la naturaleza altamente paralela de la computación realizada por el ADN para resolver problemas que son difíciles o casi imposibles de resolver utilizando los métodos tradicionales.
• Es un ejemplo de computación a nivel molecular, en la línea de la nanocomputación , y esto potencialmente es una ventaja importante en cuanto a la densidad de información en los medios de almacenamiento, que nunca podrá ser alcanzada por la industria de los semiconductores.
• Demuestra aspectos únicos del ADN como estructura de datos.

Esta capacidad de computación masiva en paralelo en la computación de ADN se puede aprovechar para resolver muchos problemas computacionales a una escala enormemente grande, como los sistemas computacionales basados ​​en células para el diagnóstico y tratamiento del cáncer y los medios de almacenamiento de densidad ultra alta. ^[2]

Esta selección de palabras clave (secuencias de oligonucleótidos de ADN) es un obstáculo importante en sí misma debido al fenómeno de la formación de estructura secundaria (en el que las cadenas de ADN tienden a plegarse sobre sí mismas durante la hibridación y, por lo tanto, se vuelven inútiles para cálculos posteriores. Esto también se conoce como autohibridación). El algoritmo Nussinov-Jacobson ^[3] se utiliza para predecir estructuras secundarias y también para identificar ciertos criterios de diseño que reducen la posibilidad de formación de estructura secundaria en una palabra clave. En esencia, este algoritmo muestra cómo la presencia de una estructura cíclica en un código de ADN reduce la complejidad del problema de probar las palabras clave para estructuras secundarias.

Las construcciones novedosas de dichos códigos incluyen el uso de matrices de Hadamard generalizadas extendidas reversibles cíclicas y un enfoque binario. Antes de sumergirnos en estas construcciones, revisaremos cierta terminología genética fundamental. La motivación de los teoremas presentados en este artículo es que coinciden con el algoritmo de Nussinov-Jacobson, en el sentido de que la existencia de una estructura cíclica ayuda a reducir la complejidad y, por lo tanto, evita la formación de una estructura secundaria, es decir, estos algoritmos satisfacen algunos o todos los requisitos de diseño para oligonucleótidos de ADN en el momento de la hibridación (que es el núcleo del proceso de computación del ADN) y, por lo tanto, no sufren los problemas de la autohibridación.

Definiciones

Un código de ADN es simplemente un conjunto de secuencias sobre el alfabeto . ${\displaystyle {\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}}$

Cada base de purina es el complemento Watson-Crick de una base de pirimidina única (y viceversa): la adenina y la timina forman un par complementario, al igual que la guanina y la citosina . Este emparejamiento se puede describir de la siguiente manera: . ${\displaystyle {\bar {A}}=T,{\bar {T}}=A,{\bar {C}}=G,{\bar {G}}=C}$

Este tipo de emparejamiento es químicamente muy estable y fuerte. Sin embargo, a veces se producen emparejamientos de bases no coincidentes debido a mutaciones biológicas .

La mayor parte de la atención que se ha dedicado a la codificación del ADN se ha centrado en la construcción de grandes conjuntos de palabras clave de ADN con propiedades de distancia mínima prescritas. Para ello, establezcamos las bases necesarias para seguir avanzando.

Sea una palabra de longitud sobre el alfabeto . Para , utilizaremos la notación para denotar la subsecuencia . Además, la secuencia obtenida al invertir se denotará como . El complemento de Watson-Crick , o el complemento inverso de q , se define como , donde denota el par de bases del complemento de Watson-Crick de . ${\displaystyle {\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q}}_{n}}$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle 1\leqslant i\leqslant j\leqslant n}$ ${\displaystyle {\mathit {q}}_{[i,j]}}$ ${\displaystyle {\mathit {q}}_{i}{\mathit {q}}_{i+1}\dots {\mathit {q}}_{j}}$ ${\displaystyle {\mathit {q}}}$ ${\displaystyle {\mathit {q}}^{R}}$ ${\displaystyle {\mathit {q}}^{RC}={\mathit {{\bar {q}}_{n}}}{\mathit {{\bar {q}}_{n-1}}}\dots {\mathit {{\bar {q}}_{1}}}}$ ${\displaystyle {\mathit {{\bar {q}}_{i}}}}$ ${\displaystyle {\mathit {q}}_{i}}$

Para cualquier par de palabras de longitud y más de , la distancia de Hamming es el número de posiciones en las que . Además, defina la distancia de Hamming inversa como . De manera similar, la distancia de Hamming de complemento inverso es . (donde representa el complemento inverso ) ${\displaystyle {\mathit {n}}}$ ${\displaystyle {\mathit {p}}}$ ${\displaystyle {\mathit {q}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathit {d}}_{H}({\mathit {p}},{\mathit {q}})}$ ${\displaystyle {\mathit {i}}}$ ${\displaystyle {\mathit {p}}_{i}\neq {\mathit {q}}_{i}}$ ${\displaystyle {\mathit {d_{H}}}^{R}({\mathit {p}},{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{R})}$ ${\displaystyle {\mathit {d}}_{H}^{RC}({\mathit {p}},{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{RC})}$ ${\displaystyle RC}$

Otra consideración importante del diseño de códigos vinculada al proceso de hibridación de oligonucleótidos se relaciona con el contenido de GC de las secuencias en un código de ADN. El contenido de GC , , de una secuencia de ADN se define como el número de índices tales que . Un código de ADN en el que todas las palabras de código tienen el mismo contenido de GC, , se denomina código de contenido de GC constante . ${\displaystyle {\mathit {w}}_{GC}({\mathit {q}})}$ ${\displaystyle {\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q}}_{n}}$ ${\displaystyle {\mathit {i}}}$ ${\displaystyle {\mathit {q}}_{i}\in \{G,C\}}$ ${\displaystyle w}$

Una matriz de Hadamard generalizada es una matriz cuadrada con elementos tomados del conjunto de las raíces unitarias, , que satisface = . Aquí denota la matriz identidad de orden , mientras que * representa la conjugación compleja. Nos ocuparemos únicamente del caso de algún primo . Una condición necesaria para la existencia de matrices de Hadamard generalizadas es que . La matriz exponencial , , de es la matriz con los elementos en , se obtiene reemplazando cada elemento en por el exponente . ${\displaystyle {\mathit {H}}\equiv {\mathit {H}}(n,\mathbb {C} _{m})}$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle \times }$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle {\mathit {m}}}$ ${\displaystyle \mathbb {C} _{m}=\{e^{-2\pi {\mathit {i}}{\mathit {l}}/{\mathit {m}}}\mid l=0,\dots ,m-1\}}$ ${\displaystyle {\mathit {H}}{\mathit {H}}^{*}}$ ${\displaystyle {\mathit {n}}{\mathit {I}}}$ ${\displaystyle {\mathit {I}}}$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle {\mathit {m}}={\mathit {p}}}$ ${\displaystyle {\mathit {p}}}$ ${\displaystyle {\mathit {H}}({\mathit {n}},\mathbb {C} _{p})}$ ${\displaystyle {p}|{n}}$ ${\displaystyle E({\mathit {n}},\mathbb {Z} _{p})}$ ${\displaystyle {\mathit {H}}({\mathit {n}},\mathbb {C} _{p})}$ ${\displaystyle {\mathit {n}}\times {\mathit {n}}}$ ${\displaystyle {\mathit {Z}}_{p}=\{0,1,2,\dots ,{\mathit {p}}-1\}}$ ${\displaystyle (e^{-2\pi {\mathit {i}}l/{\mathit {m}}})}$ ${\displaystyle {\mathit {H}}({\mathit {n}},\mathbb {C} _{p})}$ ${\displaystyle {\mathit {l}}}$

Los elementos de la matriz del exponente de Hadamard se encuentran en el campo de Galois , y sus vectores de fila constituyen las palabras clave de lo que se llamará un código Hadamard generalizado. ${\displaystyle {\text{GF}}(p)}$

Aquí, los elementos de se encuentran en el campo de Galois . ${\displaystyle {\mathit {E}}}$ ${\displaystyle {\text{GF}}(p)}$

Por definición, una matriz de Hadamard generalizada en su forma estándar tiene solo 1 en su primera fila y columna. La matriz cuadrada formada por las entradas restantes de se llama núcleo de , y la submatriz correspondiente de la matriz exponencial se llama núcleo de construcción. Por lo tanto, por omisión de la primera columna de todos ceros son posibles los códigos de Hadamard generalizados cíclicos, cuyas palabras de código son los vectores de fila de la matriz perforada. ${\displaystyle {\mathit {H}}}$ ${\displaystyle ({\mathit {n}}-1)\times ({\mathit {n}}-1)}$ ${\displaystyle H}$ ${\displaystyle {\mathit {H}}}$ ${\displaystyle {\mathit {E}}}$

Además, las filas de dicha matriz exponencial satisfacen las dos propiedades siguientes: (i) en cada una de las filas distintas de cero de la matriz exponencial, cada elemento de aparece un número constante, , de veces; y (ii) la distancia de Hamming entre dos filas cualesquiera es . ^[4] ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathit {n}}/{\mathit {p}}}$ ${\displaystyle {\mathit {n}}({\mathit {p}}-1)/{\mathit {p}}}$

Propiedadtú

Sea el grupo cíclico generado por , donde es una raíz primitiva compleja de la unidad, y es un primo fijo. Además, sea , vectores arbitrarios sobre los cuales tienen una longitud , donde es un entero positivo. Defina la colección de diferencias entre exponentes , donde es la multiplicidad del elemento de los cuales aparece en . ^[4] ${\displaystyle {\mathit {C_{p}}}=\left\{1,x,x^{2},\ldots ,x^{p-1}\right\}}$ ${\displaystyle {\mathit {x}}}$ ${\displaystyle x=\exp(2\pi ij/p)}$ ${\displaystyle p}$ ${\displaystyle p>2}$ ${\displaystyle {\mathit {A}}=(x^{a_{i}})}$ ${\displaystyle {\mathit {B}}=(x^{b_{i}})}$ ${\displaystyle \mathbb {C} _{p}}$ ${\displaystyle {\mathit {N}}=pt}$ ${\displaystyle {\mathit {t}}}$ ${\displaystyle {\mathit {Q}}=\{a_{i}-b_{i}\mod p:i=1,2,\ldots ,N\}}$ ${\displaystyle {\mathit {n_{q}}}}$ ${\displaystyle {\mathit {q}}}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle {\mathit {Q}}}$

Se dice que un vector satisface la propiedad U si y solo si cada elemento de aparece exactamente en tiempos ( ) ${\displaystyle {\mathit {Q}}}$ ${\displaystyle {\mathit {q}}}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle {\mathit {t}}}$ ${\displaystyle {\mathit {n_{q}}}=t,q=0,1,\ldots ,p-1}$

El siguiente lema es de fundamental importancia para la construcción de códigos Hadamard generalizados.

Lema. Ortogonalidad de vectores sobre – Para primos fijos , vectores arbitrarios de longitud , cuyos elementos son de , son ortogonales si el vector satisface la Propiedad U , donde es la colección de diferencias entre los exponentes de Hadamard asociados con . ${\displaystyle {\mathit {C_{p}}}}$ ${\displaystyle {\mathit {p}}}$ ${\displaystyle {\mathit {A}},{\mathit {B}}}$ ${\displaystyle {\mathit {N}}=pt}$ ${\displaystyle {\mathit {C_{p}}}}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle {\mathit {Q}}}$ ${\displaystyle \mod {\mathit {p}}}$ ${\displaystyle {\mathit {A}},{\mathit {B}}}$

Secuencias M

Sea un vector arbitrario de longitud cuyos elementos están en el cuerpo finito , donde es un primo. Sean los elementos de un vector que constituyen el primer periodo de una secuencia infinita que es periódica de periodo . Si es el periodo más pequeño para concebir cualquier subsecuencia, la secuencia se llama una M-secuencia, o una secuencia máxima de menor periodo obtenida permutando cíclicamente los elementos. Si siempre que los elementos de se permutan arbitrariamente para obtener , la secuencia es una M-secuencia, entonces la secuencia se llama M-invariante . Los teoremas que siguen presentan condiciones que aseguran la M-invariancia . En conjunción con una cierta propiedad de uniformidad de los coeficientes polinómicos, estas condiciones producen un método simple por el cual se pueden construir matrices de Hadamard complejas con núcleo cíclico. ${\displaystyle {\mathit {V}}}$ ${\displaystyle {\mathit {N}}}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle p}$ ${\displaystyle V}$ ${\displaystyle a(V)}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle a(V^{*})}$ ${\displaystyle a(V)}$

El objetivo aquí es encontrar una matriz cíclica cuyos elementos estén en el campo de Galois y cuya dimensión sea . Las filas de serán las palabras de código distintas de cero de un código cíclico lineal , si y solo si hay un polinomio con coeficientes en , que es un divisor propio de y que genera . Para tener palabras de código distintas de cero, debe ser de grado . Además, para generar un núcleo Hadamard cíclico, el vector (de coeficientes de) cuando se opera con la operación de desplazamiento cíclico debe ser de período , y la diferencia vectorial de dos filas arbitrarias de (aumentada con cero) debe satisfacer la condición de uniformidad de Butson, ^[5] anteriormente denominada Propiedad U . Una condición necesaria para la -periodicidad es que , donde es mónico irreducible sobre . ^[6] El enfoque aquí es reemplazar el último requisito con la condición de que los coeficientes del vector se distribuyan uniformemente sobre , es decir, cada residuo aparece el mismo número de veces (Propiedad U). A continuación se presenta una prueba de que este enfoque heurístico siempre produce un núcleo cíclico. ${\displaystyle {\mathit {E}}={\mathit {E_{c}}}}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle N=p^{n}-1}$ ${\displaystyle {\mathit {E}}}$ ${\displaystyle K}$ ${\displaystyle g(x)}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle {\mathit {x^{N}-1}}}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle g(x)}$ ${\displaystyle N-n}$ ${\displaystyle g(x)}$ ${\displaystyle N}$ ${\displaystyle {\mathit {E}}}$ ${\displaystyle N}$ ${\displaystyle x^{N}-1=g(x)h(x)}$ ${\displaystyle h(x)}$ ${\displaystyle [0,g(x)]}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle 0,1,\ldots ,p-1}$

Ejemplos de construcción de código

Construcción de código utilizando matrices de Hadamard complejas

Algoritmo de construcción

Considérese un polinomio irreducible mónico sobre de grado que tiene un compañero adecuado de grado tal que , donde el vector satisface la propiedad U . Esto requiere solamente un algoritmo de computadora simple para la división larga sobre . Como , el ideal generado por es un código cíclico . Además, la propiedad U garantiza que las palabras de código distintas de cero forman una matriz cíclica, cada fila de período bajo permutación cíclica, que sirve como núcleo cíclico para la matriz de Hadamard . Como ejemplo, un núcleo cíclico para resulta de los compañeros y . Los coeficientes de indican que es el conjunto de diferencias relativas, . ${\displaystyle h(x)}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle g(x)}$ ${\displaystyle N-n}$ ${\displaystyle g(x)h(x)=x^{N}-1}$ ${\displaystyle [0,g(x)]}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle h(x)|x^{N}-1}$ ${\displaystyle g(x)\mod (x^{N}-1)}$ ${\displaystyle {\mathit {K}}}$ ${\displaystyle N}$ ${\displaystyle H(p,pn)}$ ${\displaystyle H(3,9)}$ ${\displaystyle h(x)=x^{2}+x+2}$ ${\displaystyle g(x)=x^{6}+2x^{5}+2x^{4}+2x^{2}+x+1}$ ${\displaystyle g}$ ${\displaystyle \{0,1,6\}}$ ${\displaystyle \mod 8}$

Teorema

Sea un primo y , con un polinomio mónico de grado cuyo vector extendido de coeficientes son elementos de . Supóngase que se cumplen las siguientes condiciones: ${\displaystyle {\mathit {p}}}$ ${\displaystyle {\mathit {N}}+1={\mathit {pn}}}$ ${\displaystyle {\mathit {g}}(x)}$ ${\displaystyle {\mathit {N}}-{\mathit {n}}}$ ${\displaystyle C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1}]}$ ${\displaystyle {\text{GF}}(p)}$

1. vector satisface la propiedad U, y ${\displaystyle C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\dots ,{\mathit {c}}_{N-1}]}$
2. ${\displaystyle g(x)h(x)=x^{N}-1}$, donde es un polinomio irreducible mónico de grado . ${\displaystyle h(x)}$ ${\displaystyle n}$

Entonces existe un código cíclico lineal p -ario de tamaño de bloque , tal que el código aumentado es la matriz exponencial de la matriz de Hadamard , con , donde el núcleo de es una matriz cíclica. ${\displaystyle {\bar {K}}}$ ${\displaystyle N}$ ${\displaystyle K=[0,{\bar {K}}]}$ ${\displaystyle H(p,p_{n})=xK}$ ${\displaystyle x=e^{2\pi i/p}}$ ${\displaystyle H}$

Prueba:

En primer lugar, observe que es mónica y se divide con grado . Ahora, debemos demostrar que la matriz cuyas filas son palabras de código distintas de cero constituye un núcleo cíclico para alguna matriz Hadamard compleja . ${\displaystyle g(x)}$ ${\displaystyle x^{N}-1}$ ${\displaystyle N-n}$ ${\displaystyle E_{c}}$ ${\displaystyle H}$

Dado que satisface la propiedad U, todos los residuos distintos de cero de se encuentran en C . Al permutar cíclicamente los elementos de , obtenemos la matriz de exponentes deseada , donde podemos obtener cada palabra de código en permutando la primera palabra de código. (Esto se debe a que la secuencia obtenida al permutar cíclicamente es M-invariante). ${\displaystyle {\mathit {C}}}$ ${\displaystyle {\text{GF}}(p)}$ ${\displaystyle C}$ ${\displaystyle {E_{c}}}$ ${\displaystyle {E_{c}}}$ ${\displaystyle C}$

También vemos que la ampliación de cada palabra de código de mediante la adición de un elemento cero inicial produce un vector que satisface la propiedad U. Además, dado que el código es lineal, la diferencia vectorial de dos palabras de código arbitrarias también es una palabra de código y, por lo tanto, satisface la propiedad U. Por lo tanto, los vectores de fila del código aumentado forman un exponente de Hadamard. Por lo tanto, es la forma estándar de alguna matriz de Hadamard compleja . ${\displaystyle {E_{c}}}$ ${\displaystyle \mod p}$ ${\displaystyle {\mathit {K}}}$ ${\displaystyle {\mathit {xK}}}$ ${\displaystyle {\mathit {H}}}$

Así, a partir de la propiedad anterior, vemos que el núcleo de es una matriz circulante que consiste en todos los desplazamientos cíclicos de su primera fila. Un núcleo de este tipo se denomina núcleo cíclico, donde en cada elemento de aparece en cada fila de exactamente veces, y la distancia de Hamming entre dos filas cualesquiera es exactamente . Las filas del núcleo forman un código de composición constante , que consiste en desplazamientos cíclicos de cierta longitud sobre el conjunto . La distancia de Hamming entre dos palabras de código cualesquiera en es . ${\displaystyle {\mathit {E}}}$ ${\displaystyle N={\mathit {p}}^{k}-1}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathit {E}}}$ ${\displaystyle (N+1)/p={\mathit {p}}^{k-1}}$ ${\displaystyle (N+1)(p-1)/p=(p-1)p^{k-1}}$ ${\displaystyle {\mathit {N}}}$ ${\displaystyle {\mathit {E}}}$ ${\displaystyle {\mathit {N}}}$ ${\displaystyle {\mathit {N}}}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle (p-1){\mathit {p}}^{k-1}}$

Lo siguiente se puede inferir del teorema explicado anteriormente. (Para una lectura más detallada, el lector puede consultar el artículo de Heng y Cooke. ^[4] ) Sea para primos y . Sea un polinomio mónico sobre , de grado N − k tal que sobre , para algún polinomio mónico irreducible . Supóngase que el vector , con para (N − k) < i < N, tiene la propiedad de que contiene cada elemento el mismo número de veces. Entonces, los desplazamientos cíclicos del vector forman el núcleo de la matriz exponencial de alguna matriz de Hadamard . ${\displaystyle {\mathit {N}}={\mathit {p}}^{\mathit {k}}-1}$ ${\displaystyle {p}}$ ${\displaystyle {k}\in \mathbb {Z} ^{+}}$ ${\displaystyle g(x)=c_{0}+c_{1}x+c_{2}x^{2}+\dots +c_{N-k}x^{N-k}}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathit {g}}({\mathit {x}}){\mathit {h}}({\mathit {x}})={\mathit {x}}^{N}-1}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathit {h}}({\mathit {x}})\in \mathbb {Z} _{p}[{\mathit {x}}]}$ ${\displaystyle ({c}_{0},{c}_{1},\ldots ,{c}_{N-k},{c}_{N-k+1},\ldots ,{c}_{N-1})}$ ${\displaystyle {\mathit {c}}_{i}=0}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathit {N}}}$ ${\displaystyle {\mathit {g}}=({\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1})}$

Obviamente, los códigos de ADN con contenido de GC constante se pueden construir a partir de códigos de composición constante (un código de composición constante sobre un alfabeto k-ario tiene la propiedad de que el número de ocurrencias de los símbolos k dentro de una palabra de código es el mismo para cada palabra de código) sobre mediante el mapeo de los símbolos de a los símbolos del alfabeto de ADN, . Por ejemplo, utilizando un código de composición constante cíclico de longitud sobre garantizado por el teorema demostrado anteriormente y la propiedad resultante, y utilizando el mapeo que lleva a , a y a , obtenemos un código de ADN con y un contenido de GC de . Claramente y de hecho, dado que y ninguna palabra de código en no contiene ningún símbolo , también tenemos . Esto se resume en el siguiente corolario. ^[4] ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle {\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}}$ ${\displaystyle {\mathit {3}}^{k}-1}$ ${\displaystyle \mathbb {Z} _{3}}$ ${\displaystyle 0}$ ${\displaystyle {\mathit {A}}}$ ${\displaystyle 1}$ ${\displaystyle {\mathit {T}}}$ ${\displaystyle 2}$ ${\displaystyle {\mathit {G}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathit {3}}^{k}-1}$ ${\displaystyle {\mathit {3}}^{k-1}}$ ${\displaystyle {\mathit {d_{H}}}=2.{\mathit {3}}^{k-1}}$ ${\displaystyle {\mathit {\bar {G}}}={\mathit {C}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathit {C}}}$ ${\displaystyle {\mathit {d}}_{H}^{RC}({\mathcal {D}})\geq 3^{k-1}}$

Corolario

Para cualquier , existen códigos de ADN con palabras de código de longitud , contenido de GC constante y en los que cada palabra de código es un desplazamiento cíclico de una palabra de código generadora fija . ${\displaystyle {\mathit {k}}\in \mathbb {Z} ^{+}}$ ${\displaystyle \mathbb {D} }$ ${\displaystyle {3}^{k}-1}$ ${\displaystyle {3}^{k}-1}$ ${\displaystyle {3}^{k-1}}$ ${\displaystyle {\mathit {d}}_{H}^{RC}(\mathbb {D} )\geq {3}^{k-1}}$ ${\displaystyle {\mathit {g}}}$

Cada uno de los siguientes vectores genera un núcleo cíclico de una matriz de Hadamard (donde , y en este ejemplo): ^[4] ${\displaystyle H(p,p^{n})}$ ${\displaystyle {\mathit {N}}+1={\mathit {p^{n}}}}$ ${\displaystyle {\mathit {n}}=3}$

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

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

Dónde, . ${\displaystyle {g(x)}=a_{0}+a_{1}x+\dots +a_{n}x^{n}}$

De este modo, vemos cómo se pueden obtener códigos de ADN a partir de dichos generadores mediante el mapeo en . La elección real del mapeo juega un papel importante en la formación de estructuras secundarias en las palabras de código. ${\displaystyle {0,1,2}}$ ${\displaystyle {A,T,G}}$

Vemos que todas estas asignaciones producen códigos con esencialmente los mismos parámetros. Sin embargo, la elección real de la asignación tiene una fuerte influencia en la estructura secundaria de las palabras de código. Por ejemplo, la palabra de código ilustrada se obtuvo de mediante la asignación , mientras que la palabra de código se obtuvo del mismo generador mediante la asignación . ${\displaystyle {g^{(1)}}}$ ${\displaystyle 0-A;1-T;2-G}$ ${\displaystyle {g^{(2)}}}$ ${\displaystyle {g^{(1)}}}$ ${\displaystyle 0-G;1-T;2-A}$

Construcción de código mediante un mapeo binario

Tal vez un enfoque más simple para construir/diseñar palabras de código de ADN es tener un mapeo binario al considerar el problema de diseño como el de construir las palabras de código como códigos binarios, es decir, mapear el alfabeto de palabras de código de ADN en el conjunto de palabras binarias de longitud de 2 bits como se muestra: , , , . ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathit {A}}\to 00}$ ${\displaystyle {\mathit {T}}\to 01}$ ${\displaystyle {\mathit {C}}\to 10}$ ${\displaystyle {\mathit {G}}\to 11}$

Como podemos ver, el primer bit de una imagen binaria determina claramente a qué par complementario pertenece.

Sea una secuencia de ADN. La secuencia obtenida al aplicar la función dada anteriormente a , se denomina imagen binaria de . ${\displaystyle {\mathit {q}}}$ ${\displaystyle {b(q)}}$ ${\displaystyle {\mathit {q}}}$ ${\displaystyle {\mathit {q}}}$

Ahora, dejemos que . ${\displaystyle b(q)={\mathit {b}}_{0}{\mathit {b}}_{1}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-1}}$

Ahora, sea la subsecuencia la subsecuencia par de , y la subsecuencia impar de . ${\displaystyle e(q)={\mathit {b}}_{0}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-2}}$ ${\displaystyle {b(q)}}$ ${\displaystyle o(q)={\mathit {b}}_{1}{\mathit {b}}_{3}{\mathit {b}}_{5}\ldots {\mathit {b}}_{2n-1}}$ ${\displaystyle {b(q)}}$

Así, por ejemplo, para , entonces, . ${\displaystyle q=ACGTCC}$ ${\displaystyle b(q)=001011011010}$

Entonces y . ${\displaystyle e(q)=011011}$ ${\displaystyle o(q)=001100}$

Definamos un componente par como , y un componente impar como . ${\displaystyle {\mathcal {E}}({\mathcal {C}})=\{e(x):x\in {\mathcal {C}}\}}$ ${\displaystyle {\mathcal {O}}({\mathcal {C}})=\{o(x):x\in {\mathcal {C}}\}}$

A partir de esta elección de mapeo binario, el contenido de GC de la secuencia de ADN = peso de Hamming de . ${\displaystyle {\mathit {q}}}$ ${\displaystyle {e(q)}}$

Por lo tanto, un código de ADN es una palabra de código con contenido GC constante si y solo si su componente par es un código de peso constante. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {E}}({\mathcal {C}})}$

Sea un código binario que consta de palabras de código de longitud y distancia mínima , tal que implica que . ${\displaystyle {\mathcal {B}}}$ ${\displaystyle M}$ ${\displaystyle {\mathit {n}}}$ ${\displaystyle {d_{\min }}}$ ${\displaystyle {\mathit {c}}\in {\mathcal {B}}}$ ${\displaystyle {\mathit {\bar {c}}}\in {\mathcal {B}}}$

Para , considere el subcódigo de peso constante , donde denota el peso de Hamming. Elija de modo que , y considere un código de ADN, , con la siguiente elección para sus componentes pares e impares: ${\displaystyle {\mathit {w}}>0}$ ${\displaystyle {\mathcal {B_{\mathit {w}}}}=\{u\in {\mathcal {B}}:{\mathit {w_{H}}}(u)={\mathit {w}}\}}$ ${\displaystyle {w_{H}(\cdot )}}$ ${\displaystyle {\mathit {w}}>0}$ ${\displaystyle {\mathit {n}}\geq {\mathit {2w}}+\lceil {\mathit {d_{\min }}}/2\rceil }$ ${\displaystyle {\mathcal {C}}_{w}}$

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

Donde denota ordenamiento lexicográfico. El en la definición de asegura que si , entonces , de modo que las distintas palabras de código en no pueden ser complementos inversos entre sí. ${\displaystyle <_{lex}}$ ${\displaystyle a<_{lex}b}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle ab^{RC}\in {\mathcal {O}}}$ ${\displaystyle ba^{RC}\notin {\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$

El código tiene palabras de código de longitud y peso constante . ${\displaystyle {\mathcal {E}}_{w}}$ ${\displaystyle {\left\vert {\mathcal {B}}_{w}\right\vert }^{2}}$ ${\displaystyle 2n}$ ${\displaystyle n}$

Además, y (esto se debe a que es un subconjunto de las palabras de código en ). ${\displaystyle {\mathit {d_{H}}}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})}$ ${\displaystyle {\mathit {d_{H}}}^{R}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})}$ ${\displaystyle {\mathcal {B}}_{w}}$ ${\displaystyle {\mathcal {B}}}$

También, . ${\displaystyle {\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})}$

Tenga en cuenta que y ambos tienen peso . Esto implica que y tienen peso . ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle {\mathit {w}}}$ ${\displaystyle b^{RC}}$ ${\displaystyle d^{RC}}$ ${\displaystyle {\mathit {n-w}}}$

Y debido a la restricción de peso en , debemos tener para todos , . ${\displaystyle {\mathit {w}}}$ ${\displaystyle a,b,c,d\in {\mathcal {B}}_{w}}$ ${\displaystyle {\mathit {d_{H}}}(a{\bar {b}},d^{RC}c^{R})\geq 2\lceil {\mathit {d_{\min }}}/2\rceil \geq {\mathit {d_{\min }}}}$

Por lo tanto, el código tiene palabras de código de longitud . ${\displaystyle {\mathcal {O}}}$ ${\displaystyle M(M-1)/2}$ ${\displaystyle 2n}$

De esto, vemos que (porque las palabras clave del componente de se toman de ). ${\displaystyle {d_{H}}(({\mathcal {O}}))\geq {d_{\min }}}$ ${\displaystyle {\mathcal {(}}O)}$ ${\displaystyle {\mathcal {B}}}$

Similarmente, . ${\displaystyle {d_{H}^{RC}}(({\mathcal {O}}))\geq {d_{\min }}}$

Por lo tanto, el código del ADN

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

con , tiene palabras de código de longitud , y satisface y . ${\displaystyle {w_{\max }}=({n}-\lceil d_{\min }/2\rceil )/2}$ ${\displaystyle {\frac {1}{2}}M(M-1)\sum _{w=d_{\min }}^{w_{\max }}\left\vert {A_{w}}^{2}\right\vert }$ ${\displaystyle 2{\mathit {n}}}$ ${\displaystyle {\mathit {d_{H}}}({\mathcal {B}})\geq {\mathit {d_{\min }}}}$ ${\displaystyle {\mathit {d_{H}}}^{RC}({\mathcal {B}})\geq {\mathit {d_{\min }}}}$

A partir de los ejemplos enumerados anteriormente, uno puede preguntarse: ¿cuál podría ser el potencial futuro de las computadoras basadas en ADN?

A pesar de su enorme potencial, es muy poco probable que este método se implemente en computadoras hogareñas o incluso en computadoras de oficinas, etc., debido a la gran flexibilidad y velocidad, así como a los factores de costo que favorecen a los dispositivos basados ​​en chips de silicio utilizados para las computadoras actuales. ^[2]

Sin embargo, dicho método podría utilizarse en situaciones donde el único método disponible es éste y requiere la precisión asociada con el mecanismo de hibridación de ADN; aplicaciones que requieren que las operaciones se realicen con un alto grado de confiabilidad.

Actualmente, existen varios paquetes de software, como el paquete Vienna, ^[7] que pueden predecir formaciones de estructura secundaria en ADN monocatenario (es decir, oligonucleótidos) o secuencias de ARN.

Véase también

• Teoría de la codificación
• Bioinformática
• Biocomputadoras
• Gen computacional

Referencias

1. Adleman, L. (1994). «Molecular computation of solutions to combinatorial problem» (PDF) . Science . 266 (5187): 1021–4. CiteSeerX  10.1.1.54.2565 . doi :10.1126/science.7973651. PMID  7973651. Archivado desde el original (PDF) el 2005-02-06 . Consultado el 2010-05-04 .
2. Mansuripur, M.; Khulbe, PK; Kuebler, SM; Perry, JW; Giridhar, MS; Peyghambarian, N. (2003). "Almacenamiento y recuperación de información utilizando macromoléculas como medios de almacenamiento". Serie de resúmenes técnicos de la Optical Society of America .
3. Milenkovic, Olgica ; Kashyap, Navin (14–18 de marzo de 2005). Sobre el diseño de códigos para la computación de ADN . Taller internacional sobre codificación y criptografía. Bergen, Noruega. doi :10.1007/11779360_9.
4. Cooke, C. (1999). "Construcción polinómica de matrices de Hadamard complejas con núcleo cíclico". Applied Mathematics Letters . 12 : 87–93. doi : 10.1016/S0893-9659(98)00131-1 .
5. Adámek, Jiří (1991). Fundamentos de codificación: teoría y aplicaciones de códigos correctores de errores, con una introducción a la criptografía y la teoría de la información . Chichester: Wiley. doi :10.1002/9781118033265. ISBN 978-0-471-62187-4.
6. Zierler, N. (1959). "Secuencias recurrentes lineales". J. Soc. Indust. Appl. Math . 7 : 31–48. doi :10.1137/0107003.
7. "El paquete de estructura secundaria del ARN de Viena".

Enlaces externos

• Curso de Atri Rudra en la Universidad Estatal de Nueva York, Buffalo