DNA Storage?

A Universidade Charles, situada em Praga, a exemplo de diversas outras universidades de renome ao redor do mundo, instituiu recentemente um programa interdepartamental de pós-graduação na área de biologia computacional. Integrante do corpo docente, Ms. Dolejškova está atualmente interessada no problema das árvores filogenéticas, e trabalhando, portanto, com n cadeias de DNA. Para simplificar o trabalho, Ms. Dolejškova resolveu trabalhar apenas com cadeias gênicas de comprimento m (isto é, todas as cadeias possuem exatamente m bases nitrogenadas).

Um subproblema interessante envolve o armazenamento das n cadeias em disco. Até o momento, Ms. Dolejškova está utilizando um esquema ingênuo que requer n × m caracteres, além dos delimitadores. Isto é, todas as sequências são gravadas dentro de um arquivo texto, sequencialmente. Mr. Chuchle, um colega de departamento e especialista em técnicas de armazenamento, sugeriu uma alternativa que pode ser mais econômica.

Segundo Mr. Chuchle, é possível armazenar uma cadeia juntamente com informações que permitam transformá-la em outras. Mais especificamente, considere duas cadeias de DNA D₁ = ACTA e D₂ = AGTC, onde A, C, G, T representam as bases nitrogenadas adenina, citosina, guanina e timina, nesta ordem. Observe que é possível transformar D₁ em D₂ trocando-se as bases nitrogenadas C e A das posições 2 e 4 de D₁ para G e C, respectivamente. Considere agora uma terceira cadeia D3 = CGTC. E necessária apenas uma modificação para transformar D₂ em D₃ e são necessárias três modificações para transformar D₁ em D₃. Logo, é vantajoso permitir a transitividade das modificações entre as cadeias.

Ms. Dolejškova observou rapidamente que, se as cadeias envolvidas forem muito diferentes entre si, este esquema de armazenamento alternativo não oferece ganhos. Assim, em vez de adotá-lo prontamente, ela solicitou a você que construa um programa que recebe as n cadeias, e determina o número mínimo de transformações que devem ser gravadas (além de uma cadeia) para que seja possível, no futuro, obter-se novamente as n cadeias originais. Baseado no resultado fornecido por seu programa, Ms. Dolejškova vai decidir qual dos esquemas deve utilizar em cada instância de dados que tiver.