Comparando cadenas de ADN
El ADN (o en su nombre largo el ácido desoxirribonucleico) es apasionante. Es una molécula clave para los seres vivos que contiene la información para construir otros componentes celulares. Además es la responsable de la transmisión hereditaria y de que los hijos se parezcan a sus padres.
Gracias a esa transmisión hereditaria, el análisis del ADN ha servido a los científicos para desentrañar muchos misterios. Por ejemplo, gracias a algunos proyectos científicos se han podido rastrear migraciones humanas de hace miles de años en base a las similitudes y diferencias entre el ADN encontrado en distintos yacimientos. Sin irnos tan lejos, 135 años después de que tuvieran lugar los crímenes del famoso Jack el Destripador a finales del siglo XIX, varios científicos aseguraron tener pruebas de ADN que podrían demostrar su identidad. Las pruebas se basaban en la comparación entre una muestra de ADN recogida de ropa conservada del asesino y el ADN de un descendiente de uno de los sospechosos que barajó en su momento Scotland Yard.
El hecho de que el ADN de una persona sea único (exceptuando hermanos gemelos) hace que sirva también a la policía forense para esclarecer crímenes mucho más cercanos. Si se compara ADN encontrado en el lugar del crimen con el ADN de un sospechoso y resultan ser iguales, el sospechoso tendrá que dar muchas más explicaciones para salirse sin una sentencia en contra.
No obstante, determinar si dos muestras de ADN son de la misma persona no es tarea fácil pues las muestras que se recogen no están siempre completas. Para entenderlo mejor diremos que una cadena de ADN está compuesta por cuatro tipos de nucleótidos: Adenina, Citosina, Guanina y Timina (A, C, G y T). En un mundo ideal, si nos dan dos cadenas de ADN con la lista ordenada de nucleótidos que tiene cada una, basta comparar si los caracteres coinciden. En la práctica no es tan fácil pues muchas veces algunos de los nucleótidos se han perdido (principalmente en las esquinas).
Dada una serie de cadenas de ADN, para cada una de ellas ¿cuántas de las otras podrían pertenecer al mismo individuo?
Entrada
La entrada estará formada por distintos casos de prueba. Cada uno comienza con una línea que indica el número de cadenas de ADN que se darán (hasta 40.000). A continuación vendrá una línea con cada una de las cadenas, todas con la misma longitud (como mucho 50 caracteres).
Cada cadena de ADN tendrá los caracteres A, C, G y T indicando el nucleótido colocado en esa posición o un guión (-) indicando un hueco (nucleótido desconocido) en la cadena. De haber huecos o guiónes estos estarán colocados principalmente en los laterales de la cadena; en la parte central nunca habrá más de 2.
Dos cadenas pueden pertenecer al mismo individuo si en las posiciones en las que ambas tienen nucleótido conocido, este coincide.
Salida
Por cada caso de prueba se escribirá una línea con tantos números como cadenas de ADN se han dado. El número en la posición i indicará cuántas cadenas iguales a la cadena colocada en la posición i hay (sin contar a ella misma), teniendo en cuenta que los guiones se consideran igual a cualquier otro nucleótido (o a otro guión)
Entrada de ejemplo
3 --AAA- ------ -TTT-- 4 AAA -AA AA- --- 1 ACGT
Salida de ejemplo
1 2 1 3 3 3 3 0