Research On Algorithms Of Finding Tandem Reapeat In DNA Sequences

Tandem repeat finding is the most common fundamental subject of DNA sequence analysis. In the human, tandem repeat account for at least 50% or much more. Tandem repeats play a variety of roles in gene expression, regulation and evolution, and are related with some genetic disease. Further more, the technique of DNA fingerprinting is now widely used in various fields such as medical jurisprudence, etc.Thus, the research on tandem repeat is of great importance. The main research task of this thesis is about the algorithm for searching tandem repeat.1) A method for finding exact tandem repeats is proposed. This algorithm, which is based on LZ decomposition, operates on the suffix tree for a string S and finds all occurrences of tandem repeats in S in O(|S|) time. In order to enhance the efficiency of the algorithm, the suffix tree was improved. The leaf lists are stored in internal nodes of suffix tree. It avoids subtree traversal in high frequence.2) Evolutive tandem repeats with jumps which is a new type of approximate tandem repeat is introduced. Numerous algorithms searching for various kinds of repeats can not to locate evolutive tandem repeats. A new algorithm for searching evolutive tandem repeat is proposed. This algorithm based on hamming distance effectively solved the evolutive tandem repeat finding. It is O(ln2)-time for the copy length l.To demonstrate its validity and efficiency, the two algorithms has been applied to practical genome DNA sequence. The results are:the algorithm based on LZ decom-position finds more tandem repeats and the algorithm based on hamming distance solved the evolutive tandem repeat finding.