Solving DNA puzzles

The Chinese theorem first found application in solving the kind of problem that is posed by the popular mind bender called Sudoku. The way it helped was that a whole lot of possible solutions could be clubbed into one into one lot with a unique identification. This enabled classification of possible solutions and economy in the coding that had to be done for solving the problem – only the lot had to be identified, not the  individual solutions.

Scientists at Cold Spring Harbor Laboratory, New York, have used the same principles to greatly simplify the formidable task of solving puzzles of the structure of the million-unit long DNA molecule.  

Chinese remainder theorem
This was first described by the Chinese mathematician Sun Tsu in the 4th century AD as a statement of the relation between numbers, divisors and remainders. A simple relation exists between numbers that give the same remainder when divided by some number. For example, 14 divided by 3 gives a remainder of 2, just like 17 divided by 3 also gives a remainder of 2, or 38 divided by 3. We can see that the differences between the numbers, (17-14 = 3), (38-14 = 24) or (38-17 = 21) are all multiples of the divisor 3. Such numbers are called ‘congruent to the modulus of 3’.

Yet another relation is when a number gives certain remainders when divided by different divisors, like the number 25, gives a remainder of 5 when divided by 5, a remainder of 1 when divided by 8 and a remainder of 7 when divided by 9. 

Now, the Chinese remainder theorem says that we can always find a number, like 25, which gives specific remainders when divided by a set of divisors that have the property that ‘no pair of them have a divisor other than 1’.

For example, of the numbers, 10,7,33,13, no pair has a common divisor other than 1. But this is not true of 10,7,33,14, because the pair (10,14) has a divisor, 2.  
The divisors, 5,8 and 9, in our example, satisfy this condition. The condition is called being ‘pairwise coprime’.

The Chinese theorem says that if we take any number, divide it successively by divisors like this and list out the remainders, then it is possible to work out the original number! When we list out remainders, what we are actually doing is to specify the list of ‘congruent’ numbers, which would produce the same remainder, for each divisor. The theorem then says that if the divisors are pairwise coprime, there would be a common number in all the congruent lists, which would yield the right remainder with all the divisors.

Sudoku  
In the game of Sudoku, we need to create series of 9 numbers each of which satisfy conditions in a row, a column and also in a 3x3 square. Close parallels have been developed between these conditions and the conditions in the Chinese remainder theorem and the theorem has helped develop methods to solve the Sudoku puzzle or even to say whether the puzzle has more than one solution or no solution! The appearance of prime numbers in the theorem (a collection of prime numbers must be pairwise coprime) even helps crack difficult codes based on the product of two large prime numbers, a code that is used in e-commerce.The game of Sudoku, like the Rubik’s cube, has set in motion much research in mathematics, which have application in different fields, like study of networks and scheduling.

DNA sequencing
The genetic identity of any living thing is  specified by a giant molecule in the nucleus of each cell living thing. It has been established that the coding is with the help of groups of just four kinds of chemical groups that are attached, in a series, to the backbone of the DNA molecule. Each of these groups defines a specific building block, called amino acids, of proteins, and myriad proteins can be defined with different combinations of these 20 amino acids, in a row that is often millions of units long!

Now, although the structure and nature of DNA is known, getting into the details of actual sequences of triads that define amino acids is a completely different story. The structure of the DNA is at the scale of atoms and there are no forceps that can hold different portions apart.

The detailed structure has to be deduced by identifying small and invisible portions of the sequence and looking for clues of adjacent segments with the help of chemical markers and statistical methods, a virtual hunt for a needle in the haystack of millions of sections of the DNA in feverish Brownian motion.   

Theorem simplifies DNA analysis
The traditional method has been to identify individual portions of DNA, mark them in some way and then try to locate specific structures. The method has worked and much progress has been made, but it is painstaking and tedious and holds out no hope of rapid sequencing for practical use.

The New York scientists have used ideas of the Chinese remainder theorem to simplify the task of classifying and analysing millions of items of data that DNA research throws up.

The researchers can now deal with whole libraries of genetic information instead of looking at just “one genetic sequence at a time,” says Yaniv Erlich, the lead author of the paper that has appeared as the cover story of this month’s Genome Research. The method has tremendous potential for clinical applications and can be used, says Prof Hannon, leader of the group that developed the technique, to analyse specific regions of the genomes of a large population and identify individuals who carry mutations that cause genetic diseases.