Cálculo de distancia de ADN a binario [cerrado]

Si represento el ADN como valores binarios, ¿cuál es la mejor manera de calcular la distancia entre ellos?

Entonces: A = 00, T = 11, G = 01 y C = 10

La distancia de Hamming entre ATGC y TAAC es 3, sin embargo, sus representaciones binarias dan una respuesta diferente:

Distancia de Hamming de 00110110 y 11000010 = 5.

¿Cuál es la mejor manera de calcular la distancia si las bases de ADN se representan de esta manera?

Es una cuestión de informática teórica, no de biología. Estoy votando para cerrar. Deberías probarlo en cstheory.SE .
De acuerdo con @ Remi.b. Pero antes de que nos dejes, "¿Por qué querrías hacer eso?" como solía decir el soporte de TI.
Haga esta pregunta en StackOverflow, no en cstheory
Encontré una solución, la responderé cuando vuelvas a preguntar en StackOverflow
Esta es una pregunta relevante para biology.se, creo. Sin embargo, la frase "cuál es la mejor manera de calcular..." en la pregunta es engañosa. La cuestión no es cómo realizar un cálculo, sino más bien cómo representar formalmente alguna entidad biológica, de una manera biológicamente significativa. Esta es una pregunta sobre biología teórica, no sobre cs.
Encontré este problema cuando estudiaba el libro de MANowak llamado Evolutionary Dynamics. Allí, el autor introduce el concepto de espacio secuencial, donde atribuye la "imaginación" del mismo a John Maynard Smith. La discusión de Nowak es muy superficial y no incluye su pregunta, y tampoco tengo una respuesta. Pero creo que puedo hacer la pregunta un poco más clara.
Un espacio de secuencias es un espacio L-dimensional para secuencias (de ADN o lo que sea) de longitud L. Cada secuencia es un punto en ese espacio, y la posición del punto se determina de tal manera que el valor de cada posición dentro de la secuencia determina la coordenada de la dimensión correspondiente en el espacio de secuencias. El autor sugiere entonces la distancia de Hamming de secuencias dentro de este espacio de secuencias como una métrica para la similitud entre secuencias.
Estas definiciones tienen perfecto sentido, cuando las secuencias tienen elementos binarios. Y también cualquier secuencia puede ser representada por una secuencia binaria correspondiente, dice el autor, lo que implica que el resto es sencillo, si queremos extender las definiciones a cualquier secuencia biológica. Pero esta no es una tarea sencilla, como demuestra el ejemplo en la pregunta.
Cada coordenada, o posición, en la secuencia estará representada por 2 bits. Pero algunas de las bases difieren en uno de sus bits (A y G por ejemplo), mientras que algunas de ellas (A y T) difieren en ambos bits. Por supuesto, se pueden hacer muchas especulaciones sobre cómo hacerlo convenientemente, pero no hay una forma obvia, por lo que puedo ver. Una buena respuesta podría proporcionar algunos ejemplos de la literatura de dinámica evolutiva, por ejemplo, sobre cómo se hace.
Una última nota, esta es más una cuestión de dinámica evolutiva / biología teórica, que una cuestión de bioinformática. Es relevante cuando se necesita una representación formal de secuencias biológicas (principalmente con fines de simulación). Para fines más prácticos, sobre el cálculo de la distancia entre secuencias reales, la respuesta de Jack Aidley proporciona una buena base.
Gracias por decirme por qué quieres saber. Me imagino que comparar dos cadenas alfabéticas no es lo mismo que comparar dos cadenas binarias aunque hayas 'convertido' una a otra. ¿Cuál debería usarse para la comparación evolutiva? ¡Ni idea! Para responder eso, necesitaría comprender la distancia de Hanning para decidir si es aplicable o no al problema. Así que sigo pensando que necesitas un científico informático con algo de genética molecular para discutir esto.
Por cierto, no hice la pregunta.

Respuestas (3)

La mejor manera es elegir una distancia que represente lo que usted quiere en lugar de confiar necesariamente en la distancia de Hamming.

Si simplemente desea una diferencia base por base, calcule eso ( esto puede ayudar), pero también puede querer una diferencia que dependa de la probabilidad de mutar entre diferentes bases, en cuyo caso desea definir una función que traduzca la mutación en un puntuación para cada transferencia, es decir, es posible que desee anotar una desaminación de 5-metilcitosina a timina como la ocurrencia más probable. Expresar las probabilidades relativas de diferentes mutaciones no es un problema fácil, pero hay varias opciones ampliamente utilizadas .

Lo importante es asegurarse de representar la biología subyacente, no asegurarse de tener la implementación más rápida. Primero decida esto, luego el algoritmo que le brinde la mejor velocidad (además, decidir sobre ese algoritmo es un tema para Stack Overflow, no este Stack Exchange).

Esta codificación no tiene sentido ya que los nucleótidos no están en el espacio de Hamming . La distancia de Hamming entre cada dos nucleótidos es constantemente 1, pero en la codificación binaria, varía de 1 a 2.

Soy reacio a responder con código, pero parece que la comunidad decidió que era una pregunta apropiada para Biology.SE. Así que aquí está mi solución.

La idea es "comprimir" los dos bits que representan cada nucleótido, de modo que cada nucleótido aporte 0 o 1 (no más) a la distancia.

Podría usar operaciones binarias para hacer algo como esto (en Java, pero puede aplicar la lógica en cualquier idioma):

int seq1 = 54, seq2 = 194;//ATGC and TAAC
int evenBit = 0xAAAAAAAA, oddBit = 0x55555555;

int pseudoDist = seq1 ^ seq2; //Integer.bitCount(pseudoDist) is 5
int dist = ( (pseudoDist&evenBit)>>1 ) | (pseudoDist&oddBit);
int finalDist = Integer.bitCount(dist);//output 3 not five

La idea es obtener el número total de bits que son diferentes con:

seq1 ^ seq2

Pero todavía no puede contar los bits, porque en su lugar obtendrá la distancia de Hamming, por lo que debe comprimir todos los bits que corresponden al mismo nucleótido al mismo bit usando: (pseudoDist&0xAAAAAAAA>>1)y pseudoDist&0x55555555. El primero mantiene los bits en posiciones pares y el segundo los en posiciones impares.

Ahora usas evenBits | oddBits, y puedes contar los bits.

La pregunta original combina operaciones matemáticas con la distancia de edición entre dos cadenas. Una distancia de hamming es una medida de la cantidad de cambios que debe realizar para convertir una cadena en otra cadena. Convertir el alfabeto en dígitos binarios y luego sumar o restar los números no le dirá cuántas ediciones fueron necesarias.
@mdperry El hecho de que no lo entiendas, no lo invalida... Dices que es imposible, pero ¿has mirado mi respuesta, la has probado? Mira, dice que la distancia de hamming entre ATGCy TAACes 3, que es la respuesta correcta.
Si su enfoque y solución son correctos, debería ser sencillo aplicar su código a los ejemplos de esta página: en.m.wikipedia.org/wiki/Hamming_distance .
@mdperry esto no está destinado a ninguna cadena, el hecho de que solo haya cuatro estados posibles le permite simplificarlo en 3 líneas de código, que funciona para este problema en particular
En realidad, ahora estoy de acuerdo contigo: mi comentario es incorrecto, mis disculpas.
Cálculo de distancia de ADN a binario [cerrado]
RespuestasAquíPolítica de privacidad1y, 0v