Implement a program that identifies a person based on their DNA.

$ python3 dna.py databases/large.csv sequences/5.txt Lavender

Download the file that you're going to use for this problem. Extract this file and you will see a directory of sample databases and a directory of sample sequences.

Background

DNA, the carrier of genetic information in living things, has been used in criminal justice for decades. But how exactly does DNA profiling work? Given a sequence of DNA, how can forensic investigators identify whom it belongs?

DNA (you should know this from high school) is a sequence of molecules called nucleotides arranged into a particular shape (a double helix). Each nucleotide of DNA contains one of four different bases: adenine (A), cytosine (C), guanine (G), or thymine (T). Every human cell has billions of these nucleotides arranged in sequence. Some portions of this sequence (i.e. genome) are the same, or at least very similar, across almost all humans, but other portions of the sequence have a higher genetic diversity and thus vary more across the population.

One place where DNA tends to have higher genetic diversity is in Short Tandem Repeats (STRs). An STR is a short sequence of DNA bases that tends to repeat consecutively numerous times at specific locations inside a person's DNA. The number of times any particular STR repeats varies a lot among individuals. In the DNA samples below, for example, Alice has STR AGAT repeated four times in her DNA, while Bob has the same STR repeated five times.

• Alice: CTAGATAGATAGATAGATGACTA
• Bob: CTAGATAGATAGATAGATAGATT

Using multiple STRs, rather than just one, can improve the accuracy of DNA profiling. If the probability that two people have the same number of repeats for single STR is 5%, and the analyst looks at 10 different STRs, then the probability that the two DNA samples match purely by chance is about 1 in 1 quadrillion (assuming all STRs are independent of each other). So if two DNA samples match in the number of repeats for each of the STRs, the analyst can be highly confident they came from the same person.

What might such a DNA database looks like? In its simplest form, you could imagine formatting a DNA database as a CSV file, wherein each row corresponds to an individual, and each column corresponds to a particular STR.

name,AGAT,AATG,TATC Alice,28,42,14 Bob,17,22,19 Charlie,36,18,25 

The data in the above file would suggest that Alice has the sequence AGAT repeated 28 times consecutively somewhere in her DNA, the sequence AATG repeated 42 times, and TATC repeated 14 times. Bob, meanwhile, has those same three STRs repeated 17 times, 22 times, and 19 times, respectively. And Charlie has those same STRs repeated 36, 18, and 25 times, respectively.

So given a sequence of DNA, how might you identify to whom it belongs? Imagine that you looked through the DNA sequence for the longest consecutive sequence of repeated AGATs and found that the longest sequence was 17 repeats long. If you then found that the longest sequence of AATG is 22 repeats long, and the longest sequence of TATC is 19 repeats long, that would provide a good evidence that the DNA was Bob's. It's also possible that once you take the counts for each of the STRs, it doesn't match anyone in your DNA database, in which case you have no match.

In practice, since analysts know on which chromosome and at which location in the DNA an STR will be found, they can localize their search to just a narrow section of DNA. We'll ignore that detail for this problem.

Your task is to write a program that will take a sequence of DNA and a CSV file containing STR counts for a list of individuals and then output to whom the DNA (most likely) belongs.

Specification

In a file called dna.py, implement a program that identifies to whom a sequence of DNA belongs.

• The program should require as its command-line argument that name of a CSV file containing the STR counts for a list of individuals and should require as its second command-line argument the name of a text file containing the DNA sequence to identify.
  • If your program is executed with the incorrect number of command-line arguments, your program should print an error message of your choice.
  • If the correct number of arguments are provided, you may assume that the first argument is indeed a filename of a valid CSV file, and that the second argument is the filename of a valid text file.
• Your program should open the CSV file and read its contents into memory.
  • You may assume that the first row of the CSV file will be the column names.
  • The first column will be the word name and the remaining columns will be STR sequences themselves.
• Your program should open the DNA sequence and read its contents into memory.
• For each of the STRs (from the first line of the CSV file), your program should compute the longest run of consecutive repeats of the STR in the DNA sequence to identify.
• If the STR counts match exactly with any of the individuals in the CSV file, your program should print out the name of the matching individual.
  • You may assume that the STR counts will not match more than one individual.
  • If the STR counts do not match exactly with any of the individuals in the CSV file. your program should print "No match".