DNA Storage?

Charles University in Prague, by example of several other leading universities around the world, recently established an interdepartmental graduate program in computational biology. Ms. Dolejškova, member of the faculty, is currently interested in the problem of phylogenetic trees, and working with n chains of DNA. To simplify the work, Ms. Dolejškova decided to work only with gene chains of length m (i.e., all the chains have exactly m nitrogenous bases).

An interesting sub-problem involves storing the n chains in a disk. Yet, Ms. Dolejškova is using a naive scheme that requires n × m characters, besides the delimiters. I.e., all sequences are written in a text file, sequentially. Mr. Chuchle, a department mate and storage techniques expert, suggested an alternative that may be more economical.

According to Mr. Chuchle, you can store a chain and the information that allow it to transform into other. More specifically, consider two chains of DNA D₁ = ACTA and D₂ = AGTC, where A, C, G, T are the nitrogenous bases adenine, cytosine, guanine and thymine, respectively. Note that it is possible to turn D₁ into D₂ by exchanging the nitrogenous bases C and A of the 2 and 4 positions from D1 to G and C, respectively. Consider now a third chain D₃ = CGTC. Only a modification is required to turn D₂ into D₃ and three changes are required to transform D₁ into D₃. Thus, is profitable to have the transitivity of the changes between the chains.

Ms. Dolejškova quickly observed that alternative storage scheme does not offer gains if the chains involved are very different. Thus, instead of using it promptly, she asked you to build a program that receives n chains, and determines the minimum number of changes that must be written (plus a chain) to make it possible in future to obtain again the original n chains. Based on the results provided by your program, Ms. Dolejškova will decide which system should be used in each instance of data.