基于片段重叠群的含有重复基因的双面基因组片段填充方法和装置

摘要

本发明公开了一种基于片段重叠群的含有重复基因的双面基因组片段填充方法及装置。该方法主要包括以下步骤：计算获得缺失基因集合；对最大缺失基因串分类，将基因元素分为三种类型：n‑Type‑1串、n‑Type‑2串和n‑Type‑3串，其中n为缺失基因串的长度；对最大缺失基因串与重复基因的关系分类，将基因元素与重复基因的关系分为三种类型：无相关、半相关和相关，无相关是指插入串与重复基因不相邻且插入位置与重复基因无涉及，半相关是指插入串与重复基因不相邻且插入位置可能会与重复基因有涉及关系，有无涉及插入位置替代，相关是指插入与重复基因相邻或插入位置与重复基因完全涉及；搜索无相关和半相关类型的插入串，执行无相关和半相关串插入算法；对相关类型串构造辅助图，利用回溯算法和最大匹配算法进行插入。该填充方法填充速度快，效率高。本发明基于片段重叠群进行基因组填充，能够提高填充准确率和完备率，更具有一般性和实用性。