基于邻接的单面基因组片段填充问题研究进展

李春良 宋卫星 徐勤业 贾瀚栋 李晓峰 柳 楠

(山东建筑大学计算机科学与技术学院 山东 济南 250101)

0 引 言

近年来，随着基因测序技术[1-3]不断发展，基因组测序的成本已大大降低，但仅依靠基因测序技术得到一个完整的基因组序列仍是困难的。而许多研究和应用领域仍需要完整的基因组序列，如计算两个基因组之间的最小反转距离。因此，人们围绕由计算机协助完成不完整基因组的片段填充问题展开了一系列的研究。

基于无重复基因的多染色体基因组，Munoz等[4]首先提出了基因组片段填充问题，给定一个完整基因组序列A和一个不完整的基因组序列B，将缺失基因插入B中得到B′，计算A和B′的距离。其中的距离包括断点距离和二次切割与连接(DCJ)距离[5]。Yancopoulos等[5]提出了基于这两种距离的线性多项式时间精确算法。此后，文献[6]使用简单的断点距离作为相似性度量，该问题也被证明为多项式时间可解的。

当填充基因组中包含重复基因时，这个问题的解决变得困难，因为缺失基因插入位置的选择更多。基于断点距离[7-11]、基因组抽样距离[12-13]和最小公共字符串划分距离[14]这三种类型距离的片段填充问题已被证明是NP完全问题。基于基因抽样距离的片段填充问题甚至是不可近似的[15-16]。有重复基因的基因组片段填充问题可以设计出具有近似性能比的算法。本文重点讨论最大化邻接的单面基因组片段填充问题。其中，单面无重复基因组片段填充问题已经被证明是多项式时间可解的[6-7,17]；……