0 引言

介绍了基因组框架填充问题的研究背景和现状。基因组框架填充是利用计算机技术填补生物测序技术产生的基因缺失，以获得与参照基因组更近似的完整基因组序列。问题可分为单面和双面两种类型。单面问题中包含一条参照基因组和一条待填充基因组框架，而双面问题中两条序列均为待填充基因组框架。现有研究主要针对单面问题，提出了基于不同度量标准的多项式时间算法和近似算法。但含重复基因的基因组框架填充问题通常是NPC完全问题，不存在多项式时间可解的精确算法。本文将重点研究限制插入位置的含重复基因的单面基因组框架填充问题，介绍问题定义，分析现有算法，并提出解决思路和未来研究方向。

1 相关概念

介绍了基因信息的分类，包括有符号基因和无符号基因，以及基因方向的表示方法。基因和基因组用字母和数字表示，其中基因集合Σ由所有字符组成，P为排列，A为序列。研究重点为包含重复基因的序列A。定义了基因对、公共邻接和断点的概念，并介绍了基于contig的基因框架填充问题，其中缺失基因的插入位置受限于contig的两端。基因串根据插入后产生的公共邻接数量分为n-type-Ⅰ、n-type-Ⅱ和n-type-Ⅲ三种类型，分别对应不同的slot类型。此外，还定义了块和块匹配的概念。

2 问题描述

介绍了限制插入位置的单面基因组框架填充问题（L-slot-One-sided-SF-max），包括基于contig和基于块匹配的两种情况。问题目标是将缺失基因插入到基因组框架S的slot中，使得与完整基因组G的公共邻接数量最大化。在基于contig的情况下，缺失基因只能在contig之间的slot插入；而在基于块匹配的情况下，需要先计算块匹配集合，然后只能在基因串两端或与未匹配基因组合成新的块匹配来插入缺失基因。

3 算法介绍

L-slot-One-sided-SF-max问题属于NPC问题，目前主要通过FPT算法和近似算法进行求解。在FPT算法方面，Jiang等设计了以最大公共邻接数k为固定参数的算法，而Block-m-One-sided-SF-max问题的FPT算法研究相对较少。近似算法方面，Jiang等提出了2-近似算法，Feng等提出了2.57-近似算法，均以最大公共邻接数为度量标准。Ma等提出了1.71-近似算法，以最大保留有序对数为度量标准。

Contig-One-sided-SF-max问题中，Jiang等提出的k-FPT算法通过彩色编码技术和有界度搜索，将问题简化为k-path问题。2-近似算法使用贪婪策略和最大匹配处理不同类型基因串的插入，但未考虑冗余公共邻接的处理。2.57-近似算法通过构造辅助图和删除冗余匹配对来避免冗余公共邻接问题，但算法近似性能并不理想。

Block-m-One-sided-SF-max问题中，Ma等提出的1.71-近似算法引入了最大保留有序对数这一新的度量标准。该算法通过贪婪插入1-好串、扩展缺失基因等方式填充基因框架，但不含1-好串的实例中存在局限性。为解决这一问题，本文提出ex-block-m算法，通过扩展块匹配长度增加保留有序对的数量，近似比为2。

综上所述，2-近似算法和2.57-近似算法在计算最大匹配时无法实现缺失基因、插入位点以及断点之间的一一对应关系。1.71-近似算法虽能处理该问题，但在不含1-好串的实例中存在局限性。以最大保留有序对数为度量标准，设计一种普适且高效的近似算法是值得研究的问题。

4 总结与展望

总结了限制插入位置的单面基因组框架填充问题的研究背景、发展历程和当前代表性算法。提出了未来研究方向：1) 优化FPT算法参数以降低运行时间，采用递归方法解决Block-m-One-sided-SF-max问题；2) 针对Contig-One-sided-SF-max问题，深入分析问题特性，寻找更有效的近似策略，引入新算法思想，进行参数化分析；3) 对于Block-m-One-sided-SF-max问题，增加从初始块匹配右端扩展的步骤，考虑负向有序对，设计针对负向基因串的处理机制，提升近似算法性能。