Pcr Primer Design

The idea of the outer amplification of nucleotide was first proposed by Khorana and his colleagues in 1971. However, it was turned into reality after Mullis, the leader of Heredity of Humanity Library which belonged to the PE-Cetus Corporation, devised the epoch-making Polymerase Chain Reaction (PCR) in 1985. There are many distinct merits in the PCR technology, such as specialization, sensitivity, high productivity, celerity, convenience, good reproductivity, automatization and so on. As a result, PCR has been widely applied in many fields, which in turn stimulates research of molecular biology and correlative disciplines. From above mentioned , it will not be presumptuous to say that the technology of PCR is a revolutionary innovation and landmark in the field of biological medicine. Primer is the key of specific reactions of PCR. With the development of the PCR technology, primer design has become an important issue. In this dissertation, some problems and algorithms of PCR design are discussed in detail and several effective algorithms are put forward and realized.The background and some conceptions in the design of PCR primer are introduced briefly at first. Also the principle and characteristics of PCR technology are analyzed and the importance of research of primer design are addressed. Then the problems such as the selection of primer, the degenerate primer design and the arbitrary primer design are investigated.On the selection of primer in PCR experiments, we prove that minimizing the number of primers needed for amplification of a collection of DNA sequence is NP-complete. Then we design and implement a branch-and-bound algorithm and a greedy heuristic approximation algorithm. In addition, we discuss the WOPC problem which optimizes not only the number of primers but also the sum of the weights of these primers.On the degenerate primer design, we prove that this problem and several simplified ones are all NP-complete. However, these problems are polynomial solvable for some instances with limitations. Then a polynomial approximationalgorithm for solving one of the simplified degenerate primer are design.On the arbitrarily primer design, according to the general design principle, we put forward a kind of statistical algorithm based on the thought of Hash. By virtue of establishing appropriate data structures and Hash functions, we can compute the frequency of occurrence of primer in genome very quickly, which provide a powerful apparatus for the selection of primer in genomics.