Print

Scheld, Jessica M.

Mathematics

2007

MS

DNA sequencing is a common lab technique used by scientists to determine the exact order of nucleotides in a strand of DNA. Large DNA molecules are sequenced in short random overlapping fragments which are then used to assemble the entire sequence. We are interested in determining how probable a fiagrnent sequence is to being correctly assembled in the proper location. In order to do this, we must consider the DNA assembly path, and calculate the points at which there is a likelihood of failure. "Many gaps will need to be filled in, and there are areas where sequences are repeated many times, making it almost impossible to determine where some of the fragments belong [N01]."
Inherent in all DNA sequences is the occurrence of repeated subsequences, which implies a possibility of incorrectly rearranging the sequence unknowingly. This probability increases as the DNA strand increases in length. Scientists would benefit from knowing that the assembled sequence has the highest probability of being the correct one. The BEST Theorem provides a way to determine the number of Eulerian circuits given a graph with n vertices. We are interested in a more structural classification; namely, to characterize all 4-regular graphs with m Eulerian circuits. The answer would enable us to establish the probability of finding the correct DNA sequence. In this paper we address some of the characterizations of graphs which give rise to certain numbers of Eulerian circuits.