Identificador: asma-aau
Introducción
Los biólogos son capaces de describir los genes especificando secuencias completas de cuatro letras A, T, G y C, que representan los cuatro nucleótidos adenina, timina, guanina y citosina, respectivamente. La experiencia permite conocer la frecuencia de aparición de cada una de las letras A, C, T y G, esto es, A es la que aparece con más frecuencia, seguida de C y A aparece mucho más que T y G juntas. De tal manera que el código binario más eficiente para codificar estas secuencias sería:
A --> 0 C --> 10 T --> 110 G --> 111
Para este esquema de codificación, la secuencia AAACAGTAAC se codificaría como:
0001001111100010
Sin embargo, para lograr este ahorro, hemos hecho la decodificación más difícil. Tenemos que decodificar examinando los dígitos en grupos de tres.
Consideremos la secuencia 0001001111100010. Observemos los tres primeros dígitos: 000. Puesto que las palabras codificadas tienen 1, 2, o 3 dígitos y ni 00, ni 000 son palabras codificadas, la secuencia 000 sólo puede representar las tres palabras codificadas 0, 0 y 0. Veamos ahora los tres dígitos siguientes: 100. De nuevo, puesto que ni 1 ni 100 son palabras codificadas, la secuencia 110 representa dos palabras codificadas, 10 y 0. Los siguientes tres dígitos, 111, solamente pueden representar la palabra codificada 111, puesto que las otras tres palabras codificadas contienen al menos un cero. Considera ahora la secuencia 110. Puesto que ni 1 ni 11 son palabras codificadas, la secuencia 110 solamente puede representar a ella misma. Continuando de esta manera podemos decodificar la secuencia entera para obtener AAACAGTAAC.
La siguiente observación puede simplificar el proceso de codificación. Observa que 0 solamente ocurre al final de una palabra comprimida. Por tanto, cada vez que aparece un 0 es el final de una palabra codificada. Además, la única posibilidad de que aparezcan tres unos consecutivos es que la palabra codificada sea 111.
Tarea
Codificar o decodificar un mensaje, dependiendo de la opción que elija el usuario a través de un menú. Si se codifica un mensaje, se recibe éste y se escriben las letras correspondientes a la secuencia. En caso de decodificación, se deben reconocer las letras a partir de la codificación y escribir la secuencia original.
Ejemplo de muestra
Que deseas hacer?
C)odificar
D)ecodificar
T)erminar
Opcion --> c
Dame una secuencia: AGAACTAATTGACA
01110010110001101101110100
Que deseas hacer?
C)odificar
D)ecodificar
T)erminar
Opcion --> d
Dame una secuencia: 01110010110001101101110100
AGAACTAATTGACA
Que deseas hacer?
C)odificar
D)ecodificar
T)erminar
Opcion --> t
Presione una tecla para continuar . . .