没有合适的资源?快使用搜索试试~ 我知道了~
⊇可在www.sciencedirect.com在线获取理论计算机科学电子笔记322(2016)35-50www.elsevier.com/locate/entcs利用叶插入修正基因树:复杂性与近似性Stefano Beretta1迪斯科Universit`adiMilano-BicoccaMilano,Italy里卡多·唐迪2贝尔加莫大学人文与社会科学系意大利贝加莫摘要基因树校正最近在基因组学中引起了兴趣,因为它提供了理解基因家族进化的见解。在最近的一些基于叶子编辑操作的方法之后,我们考虑了问题的一个变体,其中基因树通过在多集合M中插入带有标签的叶子来校正。我们表明,决定是否可以通过在M中插入带有标签的叶子来校正基因树的问题是NP完全的。然后,我们考虑问题的优化变体,该优化变体要求对一个基因树,其叶子由多集合M ′标记,其中M ′M具有最小尺寸。对于这个问题的优化变体,我们提出了一个因子2近似算法。关键词:计算生物学,系统发育学,基因树校正,基因树-物种树协调,算法,计算复杂性。1引言对基因组进化的理解与识别哪些进化事件(主要是物种形成,复制和丢失,在某些模型中是横向基因转移)导致基因组进化有关[23,16]。对于一组给定的物种,一个基因家族(一组通过祖先基因的复制而产生的基因)的进化通常由基因树表示。一旦基因树被计算出来,通常是通过依赖于序列相似性的方法,它将与物种树(一种代表所分析的物种集合进化的树1电子邮件:stefano. disco.unimib.it2电子邮件:riccardo. unibg.ithttp://dx.doi.org/10.1016/j.entcs.2016.03.0041571-0661/© 2016作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。36S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)35以确定在所考虑的基因家族的进化中发生了哪些进化事件[24,26]。物种树是仅基于物种形成事件的系统发育树,因此由基因树和物种树表示的进化历史基因树和物种树的调和[7,8,9,18,25,27,31,14,3]比较了两棵树,以推断基因树中代表的一个相关的问题是物种树的推断,从一组潜在的不一致的基因树开始这个问题已经在不同的模型下进行了深入的研究(例如参见[10,22,2,30]),并且已知它是棘手的[6,22,12,4,20]。和解的主要缺点之一是,基因树通常包含改变最终进化情景的错误[19,28]。因此,已经提出了几种方法[11,15,17,29,13,21,5]来在基因树的构建之前校正基因树和解在本文中,我们考虑一种方法,旨在消除一种特殊的重复,称为非明显重复(NAD)。 NAD节点可能与基因树中的错误有关[10,29],因为它们代表基因树和物种树之间的不一致,而这与基因复制没有直接关系。因此,最近的一些基因树校正方法旨在修改给定基因树的结构,使其不包含NAD节点,通过polytomy refinement [21]或通过对错位的叶子/标签进行编辑操作(删除和修改)[29,13,5]。更确切地说,[29,5]中考虑的方法在叶子上引入了两个编辑操作(叶子删除和叶子修改)。在这里,按照类似的方法,我们介绍了第三个编辑操作的叶子,叶插入,我们考虑一个组合问题,称为LeafIns,其目的是删除NAD节点插入与一个给定的多集M标签的叶子。多重集合M表示基因树中由于重建过程中的错误而丢失的候选叶子的集合。我们考虑了LeafIns问题的计算复杂性,并在第3节中证明了它是NP完全的。然后,我们考虑这个问题的自然优化版本,称为MinLeafIns,其目的是通过插入由多集MJM标记的最小数量的叶子来纠正给定的基因树。对于这个优化问题(根据前面的结果,它是NP难的),我们在第4节中给出了一个因子为2的多项式时间近似算法。本文的结构如下。在第二节中,我们给出了基因树和物种树的一些初步定义和性质,并正式介绍了我们感兴趣的两个组合问题。在第3节中,我们证明了LeafIns问题是NP-完全的,而在第4节中,我们给出了MinLeafIns的因子2最后,我们总结了一些开放的问题。2个房间在本节中,我们首先介绍一些初步的概念,并给出我们感兴趣的两个组合问题的形式定义。令Λ ={11,12,...,l m}是一组标签,其中每个标签表示一个 差异S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)3537GADNAD不L3l1l2l4l2l1l2l3l4Fig. 1. 一个基因树G和一个物种树T。 从G的一个内部节点到另一个内部节点的虚线箭头表示它的lca映射。物种给定一个一般的根树U,我们用L(U)表示它的叶子的集合,用Λ(U)表示与L(U)相关的标签的集合,用r(U)表示U的根。 考虑树U的一个内部节点y,我们用yl(分别为yr)表示y的左子节点(分别为y r);yr和yl称为兄弟节点。此外,U[y]表示以节点y为根的U的子树。[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][1连接U的根节点和U的节点y的(唯一)路径上的节点x称为y的祖先;y称为x的后代。y的父元素z是y的祖先,使得(z,y)是U的弧。给定一个有序集L=l1,l2,.,l p∈ L,L上的毛虫U是具有p个叶子的二元根树,每个叶子与L的不同标签相关联,并且内部节点r(U),v1,.,v p−2使得:(1)存在一条路,连接r(U),v p−2,.,v1(按此顺序);(2)节点v1恰好与两个叶子相邻,标记为l1,l2,nodevi,其中1≤i≤p− 2,与单个叶相邻,标记为li+1,r(U)相邻到一片叶子上,用LP标记。接下来,我们考虑两种(有根的)二叉树,叶子标记为Λ(即这种树的每个叶子都与Λ中的标签相关联):物种树和基因树(见图1)。这两种树在允许的叶标号上是不同的。在一个由Λ标记的物种树T中,Λ中的每个标记都与一个叶子相关联。 在由Λ标记的基因树G中,Λ中的每个标记可以与至少一个叶相关联在基因树G的弧e=(u,v)中插入带有标签l的叶x包括:(1)定义G的新节点w,(2)移除弧e和(3)添加三个弧(u,w),(w,v),(w,x)。在比较基因树G和物种树T(都用Λ标记叶)时,我们考虑著名的LCA映射(最小共同祖先映射),用lcaG,T表示(见图1)。给定G的一个节点x,lcaG,T(x)=y,其中y是T中距离根最远的节点,使得Λ(T[y])<$Λ(G[x])。给定一个物种树T,当存在一个节点z∈ {xl,xr}(x的子节点),使得lcaG,T(x)= lcaG,T(z)时,G的一个节点x被定义为重复节点在这种情况下,我们说在x中发生了重复。G的一个节点,如果不是一个复制节点,就称为物种形成节点。此外,我们可以区分两种重复节点(见图1)。1为两种重复的示例重复节点x是表观重复节点(AD节点),如果Λ(G [x l])<$Λ(G [x r])/=<$。 请注意,AD节点是任何物种树的重复节点。如果复制节点不是AD节点,则称为NAD节点。基因树G38S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)35当它不包含NAD节点(因此每个节点要么是物种形成要么是AD节点)时,被称为与物种树T一致如在[10,29]中观察到的,NAD节点被认为与基因树中的错误有关。在这里,我们考虑两个组合问题,旨在修改基因树插入叶。首先,我们考虑一个决策问题,询问是否可以通过在多集M中插入具有标签的叶子来使基因树一致。问题1叶插入问题[LeafIns]输入:基因树G和物种树T,两者都由Λ标记,Λ中的标记的多集合M。输出:与T一致的基因树G,使得G通过插入|M|留下每个都用M中的标签标记。此外,我们考虑一个优化问题,问是否可以通过插入由包含M的最小多集MJ标记的叶子来使基因树一致。事实上,由于LeafIns将被证明是NP完全的,我们定义了一个优化问题,其中对标签多集基数的约束被放松。问题2最小叶插入问题[MinLeafIns]输入:基因树G和物种树T,两者都由Λ标记,A.输出:与T一致的基因树G,使得G通过在Λ中插入由标记的多集合M J标记的叶子而从G获得,其中M J<$M,并且|M J|是最低限度的。我们在本节结束时证明了NAD节点上的一些性质引理2.1考虑基因树G和物种树T,设x是G中的NAD节点。然后,在通过在G中插入叶子而获得的基因树G中,x是NAD节点或AD节点。证据由于X是NAD节点,因此其至少一个子节点w.l.o.g. xr被映射到y= lcaG,T(x)。因此,G[xr]中的每个叶插入不会将x改变为物种形成节点。此外,注意xl被映射到子树T[y]的节点。现在,考虑一些插入到G<$[xl]和G的弧(x,xr)中的叶子,使得x∈r和x∈l是x在G∈ R中的奇序. Letz=lcaG,T(x),其中z是y. 因此,x_r和x_l中的至少一个被映射到z,从而使x成为NAD或AD节点。实际上,通过y构造,x_r被映射到从y到z的路径上的节点,而x_l被映射到T[y]的节点或从y到z的路径上的节点。 如果x∈r和x∈l都映射到z的一个近似降维,则x也有同样的性质,证明就结束了。Q引理2.1的结果是基因树G的NAD节点只能被转换为通过叶插入从G获得的一致基因树G引理2.2考虑基因树G和物种树T,设x是G中的NAD节点。然后,对于每个p ∈ Λ(G[x]),可以通过插入S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)3539J在G [x]中用p标记的叶子,使得G [x]与T一致。证据设x是G的一个NAD结点.考虑子树G[xl]和G[xr],设p是Λ(G[x])中的标签。由于x是NAD节点,因此它保持Λ(G [x r])= Λ(G [x l])。想想w.l.o.g.。Λ(G [x r])的叶g标记为p。我们在G[xl]中插入具有标签p的叶子,使得由叶子插入添加的内部节点不是NAD节点,而x成为AD节点。考虑T的叶f标记为p。首先,假设存在G[xl]的内部节点y,其距离根最远,由lcaG,T映射到T的节点z,其是f的祖先。由于y是离根最远的节点,因此y的子节点不会映射到z。此外,假设w.l.o.g. p∈Λ(T[zl]);由此得出,由于y被映射到z,yr和yl(w.l.o.g.y1)被映射到z1的适当后代,而另一个节点(w.l.o.g.yr)被映射到zr的后代。考虑在弧(y,yl)中插入一个标记为p的叶子,并让w是叶子插入引入的内部节点。那么w是物种形成节点,因为它被映射到zl,而不修改yl、yr和y的映射。节点y变成AD节点,这是由于在G[xl]中插入了标记为p的叶子。假设G[xl]中没有节点y被lcaG,T映射到T的节点z,该节点z是f的祖先。然后,考虑在arc(x,xl)中插入标记为p的叶子。由叶插入引入的内部节点w是物种形成节点,因为它被lcaG,T映射到z的祖先u,使得f∈Λ(T[u]),而xl映射到z。此外,通过构造,xl,xr的映射不被修改,并且x成为AD节点。 Q3LeafIns的计算复杂性在本节中,我们考虑了LeafIns的计算复杂性,并证明了它是NP完全的。我们证明了这一结果,从最小顶点覆盖(MinVC)的立方图的减少给定一个三次图3G=(V,E),其中|= n和|E|= m,MinVC在三次图上询问是否存在G的覆盖,其大小至多为k,即是否存在子集V j <$V,其中|V J|≤ k,使得对于每个边{ u,v } ∈ E,u,v中至少有一个在V j中。| ≤ k, such that for each edge {u, v} ∈ E, at least one ofu, v is in V J. 注意,显然k≤n。此外,我们可以假设3 k-m≥0。实际上,顶点coverV最多覆盖三条边,每条边必须被因此3k-m≥ 0。我们首先定义LeafIns的实例,即两个子树G和T,以及多重集M。树T(见图2)由一条路径组成,该路径将根r(T)连接到节点s n,...,s1,即G的每个顶点都有一个;每个节点s i,1 ≤i ≤n,连接到子树T(vi),根r(T)连接到子树T(γ)。每个子树T(vi),其中1≤i≤n,由两个子树组成:左子树,它是有序集上的毛虫,和右子树,它正好有两个叶子,标记为xi,1,xi,2。[3]我们记得在三次图中,每个节点的度都是3。40S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)35SnT( γ)n−1T( v)nSIT( γ)T( vn−1)S2γ5S1T( vi)γ4T( v1)T( v2)γ3T( vi)γ2γγ1xi,4xi,3r(T)αiβixi,1xi,2图二、与三次图上的MinVC实例相关联的物种树T。Gg1,xGngi,jgp,qG(ep,q)r(G)a3k-m+(n-k)a3k-m+1G(a3k-m+(n-k))a3k-m一个2Gig1G(v)G(e1,x)G(ei,j)NADG( ei,j)G(a3k-m+1)G( a3k-m)的1G( a)的g0G( v) G( v)nG( vi)xj,3NADNADG(a3k-m+1)2 10 1G(v0)γβnNADNADγxG( vi)γ一、3NADγ1γ2γ3γ5γ4NADxn,3G( a3k-m)β1β2NADxi,2xi,3αixi,1xi,4x1, 3x3,3x5, 3xn−1,3x6,3x4, 3x 2, 3图三.与MinVC在三次图上的实例相关联的基因树G。物种形成节点表示为圆形,NAD节点表示为白色菱形,AD节点表示为黑色菱形。子树T(γ)是有序集上的毛毛虫。树G(参见图3)由左路径和右路径组成。左路对于G的每个顶点和每个边S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)3541都有一棵树,并且这些子树中的叶插入与图的覆盖有关;另一方面,右路和连接到它的子树的构建使得总数叶片插入的数量|M|. 更准确地说,左路径连接根r(G)42S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)35到节点g p,q,... g1,x,g n,.,g1,g0,(我们假设G的边是有序的,使得{v1,v x}是第一条边,{v p,v q}是最后一条边,根据G的边的某种排序)。每个结点gi,其中1≤i≤n,连接到一个子树G(vi),每个结点gi,j,其中{vi,vj} ∈E,连接到一个子树G(ei,j).子树G(v0)是有序集β1,.上的毛毛虫, β n,γn。子树G(vi),其中1 ≤ i ≤ n,是序集<$xi,2,xi,3,xi,1,α i,xi,4,γ<$i上的毛毛虫.子树G(ei,j),其中ei,j={vi,v j} ∈E,是有序集上的毛毛虫x y,x i,3,x j,3π.G的右路径将根r(G)连接到节点a3k-m+(n-k),., 的1. W.l.o.g.我们假设n是偶数。每个节点ai,其中1≤i≤ 3k-m+(n-k),连接到子树G(ai)。对于每个i,其中1 ≤i≤ 3 k−m,G(a i)是由两个毛毛虫组成的树的副本:有序集合<$x1,3,x3,3,.上的左毛毛虫,x n−1,3<$x2,3,x4,3,.上的右毛虫, x n,3π。对于每个i,满足3 k-m +1 ≤ i ≤ 3 k-m+(n-k),G(ai)是有序集上毛虫的一个拷贝。最后,我们定义了多重集M。M包含三个出现的标签xi,3,对于每个i,1≤i≤n,和四个出现的标签βi,对于每个i,1≤i≤n。我们首先陈述树G,T的一些性质(见图1)。2和图3)。注1设G是三次图,(G,T,M)是LeafIns的关联实例.则每个G(v i)中有3个NAD节点,1 ≤i≤n,每个G(e i,j)中有1个NAD节点,{v i,v j}∈E,每个G(ai)中有1个NAD节点,1 ≤i≤ 3 k-m,每个G(ai)中有3个NAD节点,3 k-m +1 ≤i≤ 3 k-m+(n-k)。每个节点gi,其中1 ≤i≤n,是AD节点,每个节点gi,j,其中{vi,v j}∈E,是AD节点,每个节点ai,2 ≤i≤ 3 k-m,是AD节点(a1是NAD节点)。 每个节点ai,其中3 k-m +2 ≤ i ≤ 3 k-m+(n-k),是AD节点,而节点a3k-m+1是物种形成节点。约简的主要思想是在M中插入带有标签的叶子,使得G中的NAD节点成为AD节点。每个子树G(vi),其中1≤i≤n,可以通过两种可能的方式(见引理3.1)本质上与T一致:或者插入三个标记为xi,3的叶子(这对应于顶点vi不在G的顶点覆盖中的情况),或者插入四个标记为βi的叶子(这对应于顶点vi在G的顶点覆盖中的情况)。G(ei,j)的单个NAD节点(见引理3.2和引理3.5)通过插入一个标记为xi,3或xj,3的叶子(取决于vi或vj在G的顶点覆盖中的事实)而成为AD节点。每个子树G(ai),1≤i≤ 3k-m,通过插入一个标记为xj ,3的叶子,1≤j≤n,使其与T一致,其中xj,3不用于标记G(vj)或G(ej,h)的任何插入每个子树G(ai),3k-m +1≤i≤ 3k-m+(n-k),通过插入四个标记为βj的叶子,使其与T一致,其中1≤j≤n,其中βj不用于标记G(vj)的任何插入的叶子。现在,我们准备证明减少的细节。其次,我们给出子树G(vi )和G(aj)的一些性质.S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)3543- ≤ ≤ − −∈xi,2xi,3xi,3xi,1图四、一个子树G(vi)通过插入三个标记为xi的叶子,使其与T一致,3。βixi,3图五. 通过插入四个标记为βi的叶子而使G(vi)与T一致的子树。G( ai)3k-m+ 1≤i≤ 3k-m+(n-k)ADADADβjγ2βjγ1γ5γ4βj βjγ3见图6。 一个子树G(ai),具有3km+1i3km+(nk),通过插入四个标记为β j的叶子使得G(ai)与T一致.注2设G是三次图,(G,T,M)是LeafIns的关联实例. 然后又道:• G(v i),其中1 ≤ i ≤ n,可以通过插入三个标记为x i,3的叶子来使其与T一致(见图2)。4)或插入四个标记为βi的叶子(见图4)。 5)。• G(a i),1 ≤ i ≤ 3 k-m,可以通过插入一个标记为x j,3的叶子,使其与T相容,其中1≤j≤ n。• G(ai),其中3 k-m +1 ≤ i ≤ 3 k-m+(n-k),可以通过插入四个标记为β j的叶子,其中1 ≤j ≤n,使其与T相容(见图6)。此外,我们可以证明子树G(vi)的以下性质,其中1≤i≤n。引理3.1给定顶点v iV,设G(v i)是G的对应子树。然后通过插入三片叶子或插入三片叶子得到一个与T一致的子树G_i(v_iG( vi)ADADγADxi,3xi,4xi,3αiG( vi)ADADγADβixi,4βiαixi,2βixi,144S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)35∗∗标记为x1,3或插入至少四片叶子。证据由注释2可知,从G(vi)开始,通过插入三个标记为xi,3的叶子,可以计算与T一致的子树G(vi)。很容易看出,如果通过只插入叶子来计算与T一致的子树G(vi),标记为y,其中y∈M且y=四个零,因为y∈/Λ(G(vi))。xi,3,则G(vi)可以通过插入最后,假设子树G(vi)是通过在G(vi)中插入至少一个由xi,3标记的叶子(并且最多两个叶子)和至少一个由xi, 3标记的叶子而获得的。y,其中y∈M且y=xi,3.现在,考虑G(vi)的三个NAD节点(参见注1)。由于至多有两个插入的叶子被标记为xi,3,所以G(vi)中一定存在一个节点,其左子树和右子树都包含被标记为y的叶子。对于G(vi)的每个其他NAD节点,必须插入至少一个叶(标记为xi,3或标记为与xi,3不同的标记),并且引理如下。Q其次,我们证明了子树G(ei,j)的一个性质。引理3.2设边{vi,v j} ∈ E和G中相应的子树G(ei,j)。 然后通过在G(ei,j)中插入一个标签为{xi,3,xj,3}的叶子或至少两个叶子来获得与T一致的子树G(ei,j)。证据注意,G(ei,j)包含一个NAD节点(参见注释1),可以通过插入标记为xi,3(分别为xj,3)的叶作为标记为xj,3(分别为xi,3)的G(e i,j)的叶的兄弟来使该NAD节点成为AD节点最后,由于Λ(G(ei,j))<$M={xi,3,xj,3},如果在G(ei,j)中没有插入具有{xi,3,xj,3}中的标签的叶子,则子树通过在G(ei,j)中插入至少两个叶来获得与T一致的G(ei,j)。 Q其次,我们证明了实例(G,T,M)上的LeafIns的解在子树G(vi),其中1≤i≤n,和G(ei,j),其中{vi,vj}∈E中必须插入的叶数的一个界.引理3.3给定一个三次图G和对应的LeafIns实例(G,T,M),实例(G,T,M)上的LeafIns的解G ∈ G在子树G(vi)中至多插入3(n-k)+ 4 k + m个叶子,其中vi∈ V,G(ei,j),其中{vi,v j} ∈ E。证据 设G是插入标记为M的叶子得到的与T一致的基因树。首先,注意到每个子树G(ai),其中1≤i≤ 3k-m+(n-k),可以通过插入至少4(n-k)+3k-m个叶子来使其一致。事实上,每个子树G(ai),其中1≤i≤ 3k-m,包含一个NAD节点,并且需要至少一个叶插入,而每个子树G(ai),其中3k-m +1≤i≤ 3k-m+(n-k),包含四个NAD节点,并且需要至少四个叶插入。 以来|M |= 7 n,子树G(v i),其中1 ≤i≤n,和G(ei,j),其中{v i,v j}∈E,必须通过插入最多7 n −(3 k-m +4(n-k))=3 n + m + k = 3(n-k)+4 k + m个叶而与T相容。Q引理3.4给定一个三次图G和对应的LeafIns的实例(G,T,M),实例(G,T,M)上的LeafIns的解G_n至少包含(n-kJ)个子树G_n(vi),其中1≤i≤n且kJ≤k,其中至多插入三个叶子S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)3545G∗且至多有(k-kj)个子树G<$(ei,j),{vi,v j} ∈ E,其中至少插入两个叶子.证据考虑实例(G,T,M)上的LeafIns的解G_n注意(n-kJ)≥(n-k),否则,根据引理3.3,G不能是实例(G,T,M)上的LeafIns的解。设G∈E中存在mJ个子树G∈(ei,j),{vi,vj} ∈E,其中至少插入两片叶子因此,插入子树G(vi),其中1≤i≤n,和G(ei,j),其中{vi,vj} ∈E的叶子数至少为3(n-kJ)+4kJ +m+mJ。因为根据引理3.3,至多3(n-k)+4k+m个叶被插入子树G(vi),其中1≤i≤n,并且被插入子树G(ei ,j),其中{vi , vj} ∈E , 则 3 ( n-kJ ) + 4kJ+m+mJ≤ 3 ( n-k ) + 4k+m , 这 意 味 着3n+kJ+m+mJ≤ 3n+k+m,因此mJ≤(k-kJ)。Q在下一个引理中,我们证明了在实例(G,T,M)上的LeafIns的解中,{vi,vj} ∈E的每个子树G(ei,j)本质上是通过插入一个标记为xi,3或xj,3的叶子来修改的。引理3.5给定一个三次图和对应的LeafIns的实例(G,T,M),考虑实例(G,T,M)上LeafIns的一个解G_n。然后,存在实例(G,T,M)上的LeafIns的解G +,使得对于每个{vi,v j} ∈ E,由xi,3或由xj,3标记的单个叶子已被插入G+(ei,j)中。证据 设G是实例(G,T,M)上LeafIns的解.考虑kJ个子树G(v i),其中1 ≤ i ≤ n,其中插入了三个叶子。设存在两棵子树G(vi)和G(vj),其中1≤ij≤n<且{vi,vj} ∈E,其中插入三个叶子通过构造和引理3.2,可以得出子树G(ei,j)是通过插入至少两个叶子而获得的。我们计算实例(G,T,M)上LeafIns的一个解G +,使得如果通过插入恰好三个lea得到两个子树G+(vi)和G+(vj),则{vi,vj}∈/E.定义如下三个子树集合FI,FC,FE,使得FI包含所有插入了三个叶子的子树G_i(vi),FC初始为空,FE包含子树G_i(ei,j),使得G_i(vi)和G_i(vj)都存在于FI中. 从FI,FC,FE出发,用迭代过程计算三个集合FI,Q,FC,Q,FE,Q,当FE不为空时,在F E中选取一个子树G(ei,j),将树G(vi)和G(vj)中的一个放入FC中,并将其从FI中取出. 然后,该过程更新FE,即,它移除那些子树G∈(ei,j),使得至多G(vi)和G(vj)中的一个延伸到FI。当过程终止时,考虑从FI,FC,FE获得的集合FI,Q,FC,Q,FE ,Q。注意,通过构造FE,Q是空的。 由于在每一步骤中,至少一棵树从F E中移除,并且恰好一个子树被添加到FC(并且从F I中移除),因此以下权利要求成立。索赔3.6|F、C、Q|≤|FE|和|FI|−|FI,Q|≤|FE|.因为根据引理3.4,|FE|最多为k-kJ,则由权利要求3.6得出,|FI| −|FI,Q|≤|FE|≤k−kJ。 这是我的梦想这是我的梦想|FI,Q|≥(n-kJ)-(k-kJ)=n-k。46S. 贝瑞塔河Dondi/理论计算机科学电子笔记322(2016)352∈∗∗在不失去一般性的情况下,我们假设,|FI ,Q|=n−k(否则可以从FI ,Q中删除一些子树)。现在,我们可以定义LeafIns的解G+如下:• 对FI,Q中的每一个子树G_i(vi),通过插入三个标号为xi,3的顶点来构造G~+(vi),使得G~+(vi)与T一致(见注2);• 对于每一个其他的子树G(vi),通过插入四个标记为βi的叶子来计算G+(vi),使得G+(vi)与T一致(参见注释2);• 对于每个子树G(e i ,j),通过插入一个标记为yxi ,3,ifGi(vj )isinFI,Q或yxj,3,ifGi(vi)isinFI,Q的叶子来计算G +(e i,j),因此G+(ei,j)与T一致(参见引理3.2)。 注意,通过构造,G(vi),G(vi)中至多有一个延伸到FI,Q;• 对于每个子树G(ah),1 ≤ h ≤ 3k-m,插入一个叶xi,3,其中G(vi)不在FI,Q中,并证明fxi,3的一个发生没有与子树G+(ei,j)或不同子树G(aq)中的插入叶相关联,其中1 ≤ q ≤ 3k-m,使得所得子树G+(ah)与T一致(见注2)。这是可能的,因为3(n-k)+m个标签xi,3用于G+(vi)和G+(ei,j)中的子树中的叶插入,而M包含3n个标签xi,3,对于某些i,其中1≤i≤n;因此3n-(3n-3k+m)个标签可以用于树G(ah),其中1 ≤ h ≤ 3k-m,并且因为在三次图m =3 n中,可以得出存在2m-2m+3k-m = 3k-m个标签xi,3,每个标签用于子树G+(ah)中的叶插入,其中1≤h≤3k-m;• 对每一个子树G(ah),其中3k-m+1≤h≤3k-m+(n-k),在FI,Q中插入4个leavβi,使G(vi)在其中3k-m+ 1≤p≤3k-m+(n-k)的某个子树G(ap)中不与插入的lea v相关联,从而使所得到的子树G+(ah)与T相容(见注2).这是可能的,因为|FI ,Q|=n-k,因此存在四个(n-k)la bels βi 的 同 时性,用于子树G+(aj)中的叶插入,其中3k-m≤j≤3 k-m+(n-k)。由于G+与T相容,引理成立。Q现在,我们准备介绍还原的主要结果引理3.7设G是一个三次图,(G,T,M)是LeafIns的对应实例。 存在MinVC在大小为k的三次图上的解当且仅当存在实例(G,T,M)上的LeafIns的解G。证据(10)考虑G的一个由k个顶点组成的顶点覆盖VJ(如果|VJ|
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功