基因组重组比较算法与复杂性研究

研究基因组重组排序类问题的算法与复杂性。证明无向基因组Translocation排序的计算复杂性和近似计算复杂性，设计该问题1.75近似度多项式时间近似算法。设计无向基因组Reversal+Translocation排序1.5近似度多项式时间近似算法。证明Transposition排序的计算复杂性，设计该问题改进多项式时间近似算法。设计有向基因组Reversal+Transposition排序的多项式时间精确算法，设计无向基因组Reversal +Transposition排序1.5近似度多项式时间近似算法。重组排序计算结果直接用于度量两种生命的特征差异，推导两者的演化关系。研究生命的演化关系和演化规律，在农业生产、疾病防治、医药设计中具有显著应用价值。快速有效的生命信息比较计算方法已经成为分子生物学和医学研究与实践中探索生命演化规律的重要工具。