Some Combinatorial Problems In Bioinformatics

Many problems in life science or bioinformatics can be translated into combinatorial problems of mathematics and computer science on sequences, trees and stings. What were concerned in this paper is two important issues motif finding and RNA folding. These two problems can be described in short as finding common section in many biologic sequence.Recent years, the high-speed development of life science brings large number of biologic dates to our research. How to dig valuable information from these huge number of dates became the main concern of scientists, and this actuality correspondingly developed the new subject bioinformatics which investigate the essence of life on the date obtained in biological laboratory using mathematic tool and computer science.The first problem concerned in our thesis is motif finding. In biology, gene activity is often regulated by binding transcription factors to short fragments in DNA sequences called motifs. The problem motif finding is to find these common short fragments in DNA sequences. However, motifs are subject to mutations and usually don't appear exactly. A natural model is to allow the unknown pattern to appear with some number of mismatches, insertions, and deletions in sample DNA sequences. The motif finding problem can be formulated as follows: given a set of sequences and unknown pattern (substring) that is implanted at different unknown positions with some mutations (each such implantation is called a motif), can we find all the motifs? Motif finding in unaligned DNA sequences is a fundamental problem in computational biology with important applications in understanding gene regulation. Biological approaches for this problem are tedious and time-consuming. Large amounts of genome sequence data and gene expression micro-array data let us solve this problem computationally. Most computer science problems of this sort are NP-complete. Many heuristic approaches have been developed in the last decade, but the problem is far from being solved.