DNA序列中串联重复体查找算法研究

发布时间：2018-05-18 10:09

本文选题：串联重复体 + LZ分解　；参考：《西安电子科技大学》2009年硕士论文

【摘要】：在DNA序列分析中,串联重复体查找是一个重要的基础性问题。人类DNA序列50%以上是由串联重复体组成的。串联重复体在基因表达、调控和遗传等方面起着十分重要的作用,同时它是产生多种疾病的病因。另外以串联重复体为基础的“DNA指纹技术”在法医学等领域广泛应用。因此关于串联重复的研究具有十分重要的意义。本文主要研究串联重复体查找算法。 1)针对精确串联重复体提出了一种基于LZ分解查找串联重复体的算法。对于存储在后缀树上的字符串S,该算法能在线性的时间找到所有出现在S中的串联重复体。为了进一步提高算法的效率,我们对后缀树进行了改进,给中间节点加入了叶子信息数组,这样就避免了算法对子树的遍历。 2)引入了一种新类型的近似串联重复体—进化串联重复体,由于以前提出的算法都不能解决进化串联重复体的查找问题,因此提出了基于海明距离的查找算法。对于给定的重复单元的长度l,该算法的时间复杂度为O(ln2),解决了进化串联重复体的查找问题。为了说明算法的正确性和有效性,本文将这两种分别应用于实际的基因组DNA序列,结果表明基于LZ分解的查找串联重复体方法能找到更多的串联重复体,基于海明距离的查找方法则解决了进化串联重复体的查找问题。
[Abstract]:In DNA sequence analysis, tandem repeat finding is an important basic problem. More than 50% of human DNA sequences are composed of tandem repeats. Tandem repeats play an important role in gene expression, regulation and heredity. In addition, DNA fingerprinting based on tandem repeats is widely used in forensic science and other fields. Therefore, the study of tandem repetition is of great significance. In this paper, we mainly study the algorithm of tandem repeat lookup. 1) an algorithm based on LZ decomposition is proposed to find the exact tandem repeats. For the string S stored in the suffix tree, the algorithm can find all concatenated repeating bodies in S at linear time. In order to further improve the efficiency of the algorithm, we improve the suffix tree by adding a leaf information array to the middle node, thus avoiding the traversal of the algorithm to the subtree. 2) A new type of approximate tandem repeats, evolutionary tandem repeats, is introduced. Because the previous algorithms can not solve the problem of searching evolutionary tandem repeats, a search algorithm based on hamming distance is proposed. For a given length of repetition unit, the time complexity of this algorithm is Oan ln2n 2, which solves the problem of searching evolutionary tandem repeats. In order to illustrate the correctness and validity of the algorithm, this paper applies these two methods to the actual genomic DNA sequences. The results show that the LZ decomposition based tandem repeat finding method can find more tandem repeats. The search method based on hamming distance solves the problem of searching evolutionary tandem repeats.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：R346

【相似文献】