从90年代初开始,随着人类基因组计划的展开与深入,科学工作者发现,人类的各种遗传、性状和甚至疾病等都与基因有着密切的联系。基因的载体是染色体,即一条完整的基因序列。不同的染色体代表某个个体在不同方面的性状。以往的研究表明,对应同一性状的两个个体的染色体的基因序列的相似程度,与这两个个体的某种性状的相似程度相关。　　 本文只讨论一个基因组仅包括一条染色体的且允许同一基因组包含重复基因(但同一种基因最多出现两次)的情况。1999年,D.Sankoff提出了一个去解决允许—条染色体上有重复基因的基因组重排问题的方法,即分别生成源基因组和目标基因组的一个包含所有基因且没有重复的子串。因为生成的子串可能有多种情况,目标就是找到这样一个子串对:它包含的两个子串互相转换所需的操作步数在所有的子串对中是最少的。由此建立了这样一个比较两条染色体基因序列的相似程度问题的数学模型:假设两条待比较的染色体上所含的基因种类是相同的。每条染色体看作一个字符串,每个基因是一个字母。一条染色体上的基因可以重复,问两条染色体是否存在这样一个公共子串:子串中每种基因均出现且只出现一次。是否存在这样的公共子串从某种程度上量化了两个基因组参与某一个生物进程的共同程度。　　 本文考虑一个基因组只包含一条染色体且每种基因在每个基因组上最多出现两次的情况。首次提出了无符号的情况下,解决这个问题的一个精确算法。详细分析了它的时间复杂度,给出了它的正确性证明,用Java语言实现了它,并用随机生成的实验数据验证了该算法的性能。　　 找出两条染色体的最长公共子串的问题已经被证明了是NP-hard且具有不可近似性,因此只能设计指数算法来解决它,所以想办法减少枚举的次数是本文所述算法的核心。算法分为两部分,第一部分是涉及枚举的,时间复杂度为O(1.86n),第二部分是在多项式时间内能够完成的,时间复杂度为O(n3)。若两条染色体存在公共子串,则返回该子串;若不存在,返回no。整个算法的时间复杂度为O(n31.86n)(其中n为基因种类数)。