生物信息学是20世纪80年代末，随着人类基因组计划的不断发展，基因序列和蛋白质数据的急速增加，以及信息理论和计算机技术的不断发展而逐渐形成的。在过去的十几年中人类对生物信息学，特别是DNA和人类基因序列的研究取得了长足的发展。海量DNA序列的测试完成和发布使人们可以利用计算机技术对包括DNA、RNA和蛋白质等生物序列进行分析，为生物学家提供更多有价值的信息。 在DNA序列分析中，重复片段查找是一个重要的基础性问题。人类DNA序列50％以上是由重复片段组成的，这些重复片段隐含了大量的生物进程信息，其中包含丰富的古生物记录，并提供许多关键的生物进化线索。目前，重复片段作为一个重要的遗传标记，已广泛运用于精密遗传连锁作图、肿瘤生化研究、法医学个体识别、亲子鉴定和群体遗传学分析等领域。在这种研究背景下，本文深入研究了DNA序列中重复片段查找问题，提出了面向重复片段查找的轻量级索引结构；针对重复片段的精确和相似性查找问题设计了高效的查找算法。本文的主要贡献总结如下： (1)针对用于重复片段查找的后缀树、增强后缀数组等索引结构的空间需求过大的问题，提出了一种面向重复片段查找的轻量级索引结构，称为后继数组。设计了一种基于基数排序的后继数组建立算法，其创建效率要优于后缀树和增强后缀数组的创建算法。根据生物信息学中的应用提出了面向多序列重复片段查询的多序列后继数组索引。分析了后继数组和多序列后继数组所需存储空间，并提出了节约存储空间的有效方法。分析表明，后继数组所需的存储空间远小于后缀树、增强后缀数组等索引结构，多序列后继数组存储空间也远小于多序列后缀树的存储空间； (2)针对精确重复片段查找问题，提出了一种新的重复片段的定义，即最大模式重复片段(LPR)。与其它重复片段的定义相比，比如tandem repeat，maximalrepetition，最大模式重复片段的查找结果包含了tandem repeat、maximal repetition等概念的全部重复片段信息，并明确表达出了重复片段的模式，并从理论上证明了在长度为n的序列中，最大模式重复片段的数量是O(n)数量级的。然后提出了在后缀树上查找序列中全部最大模式重复片段的算法；设计了基于后继数组的最大模式重复片段查找算法。性能分析表明基于后继数组的最大模式重复片段查找算法的性能要优于基于后缀树的查找方法； (3)针对相似性重复片段查找问题，分别提出了基于海明距离和编辑距离的相似性重复片段查找方法。针对海明距离衡量片段间相似性的不足，提出了模式相似度和片段相似度的概念，并在此基础上提出了相似性重复片段的定义SATR，设计了基于后继数组的SATR查找算法。在基于编辑距离的相似性重复片段查找中，通过对编辑距离的分析，提出了保守字符对的概念和重复片段相似性衡量方法，这种衡量方法既表达了距离与待比较片段间长度的关系，同时又避免了片段长度的限制；针对编辑距离计算的复杂性，提出了基于频率距离、Pearson相关性以及分段频率距离(Partitioned Frequency Distance)的重复片段候选集的过滤方法。针对传统的基于滑动窗口的序列划分方法效率过低，提出将后继数组用于序列划分的新方法。