CN109584965A - 一种转基因食品的交叉式基因组重组排序方法 - Google Patents

Abstract

本发明公开了一种转基因食品的交叉式基因组重组排序方法。主要包括：将一个反转操作作用在基因片段上，形成新的染色体，并通过插入得到基因组的最优反转序列；构建染色体森林，设立间接极小子排列树，计算基因组移位删除距离公式，推导出移位插入距离公式，进行交互式移位排序；在基因组的序列上进行转位操作，通过分裂使转位排序距离最小，完成基因组转位排序。该方法具有较好的精简性和普适性，设立间接极小子排列树进行交互式反转、移位和转位排序，给出基因组重组的多项式精确算法，降低算法的时间复杂度，缩短重组的基因组排列，通过最少的操作将源基因转化为目标基因组。

Description

一种转基因食品的交叉式基因组重组排序方法

技术领域

本发明涉及基因组重组、转基因技术、生物领域，具体涉及一种转基因食品的交叉式基因组重组排序方法。

背景技术

转基因食品利用基因重组技术，在打破物种原有基因排序的基础上重新排序组合，形成我们所希望呈现出某些性状的基因组。现有的基因组重组技术时间负责度较大，而且由于缺乏对于重组分析等技术的解决方法使得基因组中几个基因位于同一个位置或者遗漏其他基因，将其结合起来仅能产生基因组的部分排序而不是最优排序，无法满足对转基因食品具有的性状的需求。

发明内容

为解决上述问题，本发明的目的在于提供一种具有较好的精简性和普适性的转基因食品的交叉式基因组重组排序方法，设立间接极小子排列树进行交互式反转、移位和转位排序，给出基因组重组的多项式精确算法，降低算法的时间复杂度，缩短重组的基因组排列，通过最少的操作将源基因转化为目标基因组。

本发明解决其问题所采用的技术方案，包括以下步骤：

A.将一个反转操作作用在基因片段上，形成新的染色体，并通过插入得到基因组的最优反转序列；

B.构建染色体森林，设立间接极小子排列树，计算基因组移位删除距离公式，推导出移位插入距离公式，进行交互式移位排序；

C.在基因组的序列上进行转位操作，通过分裂使转位排序距离最小，完成基因组转位排序。

本发明的有益效果是：

在基因组重组排序越来越重要的情况下，本发明具有较好的精简性和普适性，设立间接极小子排列树进行交互式反转、移位和转位排序，给出基因组重组的多项式精确算法，降低算法的时间复杂度，缩短重组的基因组排列，通过最少的操作将源基因转化为目标基因组。

附图说明

图1为一种转基因食品的交叉式基因组重组排序方法的整体流程图；

图2为基因组的森林结构图；

图3为基因组转位排序流程图。

具体实施方式

参照图1，本发明所述的方法包括以下步骤：

A.将一个反转操作作用在基因片段上，形成新的染色体，并通过插入得到基因组的最优反转序列；

(3)转基因食品就是人工控制基因组的序列重组，基因组重组主要有：反转、移位、转位、插入、删除，反转和转位操作是作用在单条染色体上，而移位操作则作用在两条染色体上。给定一条染色体X＝{x₁,x₂,…,x_i-1,x_i,…,x_j,x_j+1,…,x_n}，将一个反转操作r(i,j)作用在基因片段(x_i,x_i+1,…,x_j-1,x_j)上，形成新的染色体X′＝{x₁,x₂,…,x_i-1,-x_j,…,-x_i,x_j+1,…,x_n}。

X

x<sub>1</sub>

x<sub>2</sub>

…

x<sub>i-1</sub>

x<sub>i</sub>

…

x<sub>j</sub>

x<sub>j+1</sub>

…

x<sub>n</sub>

X′

x<sub>1</sub>

x<sub>2</sub>

…

x<sub>i-1</sub>

-x<sub>j</sub>

…

-x<sub>i</sub>

x<sub>j+1</sub>

…

x<sub>n</sub>

反转能够颠倒染色体上的部分基因序列，将该基因序列中基因排序倒置的同时将基因的符号变反。

(4)设立转基因生物体基因序列A和外源基因序列B之间的反转距离为d，用集合H表示即在A中又在B中的基因集合，H_A和H_B分别表示只在A中和只在B中的基因集合，去掉H_A和H_B中的所有基因，则有：

反转排序便是寻找一组使基因组A转化为基因组B最少的反转序列r。将剩余基因组A′,B′用有向图表示，结合两个有向图，构造双色图G(A′,B′)，然后将去掉的H_A和H_B中的基因放回恰当的位置，从而得到A和B的一个全排序，产生最优的反转序列。

B.构建染色体森林，设立间接极小子排列树，计算基因组移位删除距离公式，推导出移位插入距离公式，进行交互式移位排序；

(3)基因组A＝{x₁,x₂,…,x_n}中含有n条染色体，每条染色体及其所有的子序列构建染色体森林F_x，则基因组的森林为：

F_A＝F_x1∪F_x2∪…∪F_xn

如图2所示，若极小子排列是间接的，用实心圆点表示，否则用空心圆点表示。基因组的一个极小子排列是森林的一个叶子节点，叶子节点数量为L，极小子排列不包含任意其他子排列。对于基因组A和B，若都包含N条染色体和n个基因，将A重组为B所需的最小移位操作次数为：

d_t＝n-N-c+L

其中，c是基因组A和B有向图中环的数量。

(4)基因组A到基因组B′的移位删除排序操作的距离公式为：

其中，A′是基因组A去掉H_A基因剩余的基因，B′是基因组B去掉H_B

基因剩余的基因，r是间接极小子排列的个数，p是有向图中不能被消除的间接极小子排列的个数。基因组A到基因组B的移位插入排序操作的距离公式为：

基因组的移位步骤为：首先删除A中的H_A基因，执行移位排序操作，得到从A到B的删除序列，将从A到B的删除序列转化为从B到A的插入序列，然后进行回填，若开始在元素x_a、x_b中删除了基因序列片段，而x_a、x_b中如果没有集合A′中的元素序列，便回填在元素x_a、x_b之间或集合A′中的元素序列之间，否则直接回填，最后执行插入排序操作，从而得到移位排序。

C.在基因组的序列上进行转位操作，通过分裂使转位排序距离最小，完成基因组转位排序。

(3)基因组转位排序操作是在基因组A＝{x₁,x₂,…,x_n}的序列上进行转位ρ(i,j,k)将子排列{x_i,x_i+1,…,x_j-1}从排列中取出后插入到x_k-1和x_k之间，其中1≤i＜j＜k≤n+1。即将排列转换为另一个排列，转位排序便是寻找一组转位，使转位排序距离最小。若有：

x_i+1≠x_i+1

则点对(x_i,x_i+1)是断点P。因此需要减少排列中断点的数量。若排列中每个元素x_i用两个顶点表示：

l(x_i)＝2x_i-1

r(x_i)＝2x_i

且将0和2n+1分别作为第一个和最后一个顶点，可以得到包含2n+2个元素的顶点序列，P(x_i)的顶点集为{0,1,…,2n+1}。

(4)转位操作要对排列x_i进行排序，必须将其断点图P(x_i)中圈的个数c(x_i)增加到n+1，一次转位操作ρ引起圈的数量变化为：

Δc(ρ)＝c(x_iρ)-c(x_i)

一个操作在简单排列上的(x,y)序列，至少有y个是3转位，并且转位序列操作后剩下一个简单排列，其中x≥y。若一个排列对应的断点图中只包含2圈，则这样的排列为2排列，转位的简单排列与反转的简单排列相同，每个排列可以通过分裂变成简单排列。设立排列x_i包含一个长度操作3的圈C，设立断点图有两种类型的边：灰边和黑边，b₁是圈C的一条黑边，经过灰边直接和b₁连接的两条黑边为b₂和b₃，灰边g和b₂相连但不与b₁相连。则(g,b₃)分裂将圈C分裂形成一个3圈和一个(k-2)圈，重复循环分裂的过程，直至得到简单排列，从而完成基因组转位排序。

综上所述，便完成了本发明所述的一种转基因食品的交叉式基因组重组排序方法。该方法具有较好的交互性和普适性，设立间接极小子排列树进行交互式反转、移位和转位排序，给出基因组重组的多项式精确算法，降低算法的时间复杂度，缩短重组的基因组排列，通过最少的操作将源基因转化为目标基因组。

Claims (4)

1.一种转基因食品的交叉式基因组重组排序方法，其特征在于：设立间接极小子排列树进行交互式反转、移位和转位排序，所述方法包括以下步骤：

A.将一个反转操作作用在基因片段上，形成新的染色体，并通过插入得到基因组的最优反转序列；

B.构建染色体森林，设立间接极小子排列树，计算基因组移位删除距离公式，推导出移位插入距离公式，进行交互式移位排序；

C.在基因组的序列上进行转位操作，通过分裂使转位排序距离最小，完成基因组转位排序。

2.根据权利要求1所述的一种转基因食品的交叉式基因组重组排序方法，其特征在于：

所述步骤A包括：

(1)给定一条染色体X＝{x₁，x₂，...，x_i-1，x_i，...，x_j，x_j+1，...，x_n}，将一个反转操作r(i，j)作用在基因片段(x_i，x_i+1，...，x_j-1，x_j)上，形成新的染色体X′＝{x₁，x₂，…，x_i-1，-x_j，…，-x_i，x_j+1，…，x_n}，

X x₁ x₂ ... x_i-1 x_i ... x_j x_j+1 ... x_n X′ x₁ x₂ ... x_i-1 -x_j ... -x_i x_j+1 ... x_n

反转能够颠倒染色体上的部分基因序列，将该基因序列中基因排序倒置的同时将基因的符号变反；

(2)设立转基因生物体基因序列A和外源基因序列B之间的反转距离为d，用集合H表示即在A中又在B中的基因集合，H_A和H_B分别表示只在A中和只在B中的基因集合，去掉H_A和H_B中的所有基因，则有：

反转排序便是寻找一组使基因组A转化为基因组B最少的反转序列r，将剩余基因组A′，B′用有向图表示，结合两个有向图，构造双色图G(A′，B′)，然后将去掉的H_A和H_B中的基因放回恰当的位置，从而得到A和B的一个全排序，产生最优的反转序列。

3.根据权利要求2所述的一种转基因食品的交叉式基因组重组排序方法，其特征在于：

所述步骤B包括：

(1)基因组A＝{x₁，x₂...，x_n}中含有n条染色体，每条染色体及其所有的子序列构建染色体森林F_x，则基因组的森林为：

F_A＝F_x1∪F_x2∪…∪F_xn

基因组的一个极小子排列是森林的一个叶子节点，叶子节点数量为L，极小子排列不包含任意其他子排列，对于基因组A和B，若都包含N条染色体和n个基因，将A重组为B所需的最小移位操作次数为：

d_t＝n-N-c+L

其中，c是基因组A和B有向图中环的数量；

(2)基因组A到基因组B′的移位删除排序操作的距离公式为：

其中，A′是基因组A去掉H_A基因剩余的基因，B′是基因组B去掉H_B基因剩余的基因，r是间接极小子排列的个数，p是有向图中不能被消除的间接极小子排列的个数，基因组A到基因组B的移位插入排序操作的距离公式为：

基因组的移位步骤为：首先删除A中的H_A基因，执行移位排序操作，得到从A到B的删除序列，将从A到B的删除序列转化为从B到A的插入序列，然后进行回填，若开始在元素x_a、x_b中删除了基因序列片段，而x_a、x_b中如果没有集合A′中的元素序列，便回填在元素x_a、x_b之间或集合A′中的元素序列之间，否则直接回填，最后执行插入排序操作，从而得到移位排序。

4.根据权利要求3所述的一种转基因食品的交叉式基因组重组排序方法，其特征在于：

所述步骤C包括：

(1)基因组转位排序操作是在基因组A＝{x₁，x₂，...，x_n}的序列上进行转位ρ(i，j，k)将子排列{x_i，x_i+1，...，x_j-1}从排列中取出后插入到x_k-1和x_k之间，其中1≤i＜j＜k≤n+1，即将排列转换为另一个排列，转位排序便是寻找一组转位，使转位排序距离最小，若有：

x_i+1≠x_i+1

则点对(x_i，x_i+1)是断点P，因此需要减少排列中断点的数量，若排列中每个元素x_i用两个顶点表示：

l(x_i)＝2x_i-1

r(x_i)＝2x_i

且将0和2n+1分别作为第一个和最后一个顶点，可以得到包含2n+2个元素的顶点序列，P(x_i)的顶点集为{0，1，...，2n+1}；

(2)转位操作要对排列x_i进行排序，必须将其断点图P(x_i)中圈的个数c(x_i)增加到n+1，一次转位操作ρ引起圈的数量变化为：

Δc(ρ)＝c(x_iρ)-c(x_i)

一个操作在简单排列上的(x，y)序列，至少有y个是3转位，并且转位序列操作后剩下一个简单排列，其中x≥y，若一个排列对应的断点图中只包含2圈，则这样的排列为2排列，转位的简单排列与反转的简单排列相同，每个排列可以通过分裂变成简单排列；设立排列x_i包含一个长度操作3的圈C，设立断点图有两种类型的边：灰边和黑边，b₁是圈C的一条黑边，经过灰边直接和b₁连接的两条黑边为b₂和b₃，灰边g和b₂相连但不与b₁相连；则(g，b₃)分裂将圈C分裂形成一个3圈和一个(k-2)圈，重复循环分裂的过程，直至得到简单排列，从而完成基因组转位排序。