跳过主要内容

加权最小反馈顶点集及其在人类癌症基因检测中的实现

摘要

背景

最近,许多计算方法被提出来预测癌症基因。一种典型的方法是找到肿瘤和正常样本之间差异表达的基因。然而,也有一些基因,例如“暗”基因,在网络层面发挥着重要作用,但传统的差异基因表达分析很难找到它们。此外,网络可控性方法,如最小反馈顶点集(MFVS)方法,已被广泛用于癌症基因预测。然而,传统的MFVS方法忽略了顶点(或基因)的权重,由于存在许多可能的MFVSs,导致难以找到最优解。

结果

这里,我们介绍一种新颖的方法,被称为加权MFVS(WMFVS),它集成了MFVS基因差异表达值在蛋白质相互作用的网络来选择从所有可能的MFVSs所述最大加权MFVS。我们的实验结果表明,WMFVS实现比使用传统的生物数据或网络数据分析单独更好的性能。

结论

该方法平衡了差异基因表达分析和网络分析的优势,提高了差异基因表达分析的准确性,降低了纯网络分析的不稳定性。此外,WMFVS可以方便地应用于各种网络,为数据分析和预测提供了一个有用的框架。

背景

癌症是一种遗传疾病,但并非所有基因都与癌症有关。通过几乎普遍的共识,癌症现在被视为因某些关键调节基因的变化而导致[1].目前,研究人员已经定义了几种与癌症相关的基因集。一种广泛使用的基因是癌症驱动基因,它是指在体内细胞中存在的特定微环境条件下,其突变增加细胞净生长的基因。这种基因可以通过发现“显著突变基因”来预测,这些基因的突变率明显高于假定的背景体细胞突变率[23.4]. 然而,由于难以建立可靠的背景突变模型[5],用基于频率的方法选择金标准的驱动基因是困难的。另一种与癌症相关的基因是所谓的“癌症基因”,包括癌基因,它作为正生长调节因子,和肿瘤抑制基因(TSGs),作为负生长调节因子。这些基因与肿瘤和正常基因的表型直接相关,可以通过差异基因表达分析进行预测。然而,一些“黑暗”基因在网络水平上发挥着重要作用,但通常被传统的差异基因表达分析忽略[67].

利用图论算法,我们可以找到控制网络的关键顶点。例如,[8]开发了一种基于反馈的框架,可提供可实现的节点覆盖,使系统转向其自然长期动态行为之一;[9为选择关键分子控制具有反馈顶点集的系统提供了合理的准则;[10.]提出了一种网络控制策略,寻找驱动突变,使调节网络从正常状态变为疾病状态;和[11.研究了将最小反馈顶点集(MFVS)应用于真实的生物定向复杂网络,并在两者中发现了必需的蛋白质黑腹果蝇智人生物。

给定一个有向网络,反馈顶点集(FVS)是一组顶点,移除这些顶点后剩下的网络是非循环的。最小反馈顶点集(MFVS)是一种在所有可能的FVS中具有最小大小的FVS。MFVS问题已被证明是NP完全问题[12.].目前已有许多求解MFVS问题的算法,包括近似算法[13.、随机算法[14.,参数化算法[15.和精确算法[16.17.].

一般情况下,一个网络中可以有多个mfv。传统的MFVS算法忽略了可能的MFVS之间的差异,输出通常是随机的。这种随机性导致了网络分析方法在实践中的不稳定性。为了寻找多个MFVS的最优输出,本文考虑了一个MFVS问题的变化,即每个顶点都被赋予一个权值,输出值为最大的加权MFVS。所分配的权重应该反映对应顶点的重要性,这可能涉及到其他研究的一些生物数据(例如,在我们的实验中,我们使用微分表达式值来计算权重)。我们将这个问题定义为加权MFVS (WMFVS)问题。

要解决WMFV问题,我们从[中文中)修改了一个精确的算法17.,首先压缩原始图[18.19.]来减少顶点和弧的数量,然后利用整数线性规划(ILP)方法来压缩图。我们的WMFVS方法大致可以分为图压缩、MFVS尺寸确定和输出优化三个部分。前两部分使用了与[17.]第三部分使用修改的ILP方法选择最大加权MFV。

此外,我们考虑了WMFVS方法的一个变化,它更关注FVS的总权重而不是其大小;即求最大加权FVS。我们称这个方法为WFVS。在下一节中,我们可以看到WMFVS比WFVS有更高的精度,而WFVS在召回方面有优势。

结果

数据集

在这项研究中,我们使用了定向人类蛋白质相互作用网络[20.]进行分析;它包含6338个基因(顶点)和34814个定向相互作用(弧)。为了评估我们的方法和现有方法对癌症基因的相对预测准确性,我们从5个公共数据库中收集了癌症相关基因集:ONGene [21.], TSGene [22.],CGC [23.], NCG [24.]和MSigDB C6 [25.].由于数据集中并不是所有的基因都包含在定向的人类蛋白质相互作用网络中,所以我们过滤了特定数据集和网络中的常见基因。这些数据集的大小如表所示1

表1每个数据集的大小和网络中包含的基因数量(常见基因)

在本文的其余部分,当我们计算各种方法的召回时,我们只考虑常见基因集的大小。

重定义

为了确定基因的权重,我们首先从TCGA下载了RNA-seq数据[26.,其中包含了1102份乳腺肿瘤样本和113份正常样本的基因表达数据。接下来,对3级RNASeqV2数据计数进行处理和转换,然后用于进一步分析[27.].具体来说,我们使用肿瘤和正常样本之间的fold change (FC)值(使用二进制对数和绝对值)作为每个顶点(基因)的权重。一个特定的基因v,其重量通过以下公式计算:

$$ \ begin {对齐} v.w = \ left |\ frac {\ sigma _ {i = 1} ^ n \ log _2 t_i} {n} - \ frac {\ sigma _ {j = 1} ^ m \ log _2 n_j} {m} \ loct |\结束{对齐} $$
(1)

在哪里\ (T_i \)肿瘤标本的表达值是多少\ (N_j \)是否为正常样本的表达式值j,n是肿瘤和正常样品的数量。直观地,高Fc值对应于癌症基因的高可能性。因此,使用FC值作为基因的权重是合理的。

对于出现在网络中但在TCGA数据中没有表达值的基因(只有143个基因,占网络规模的2.3%;这些被称为减肥基因),我们给它们默认权重为0,而不是忽略它们;因此,如果该基因在拓扑水平上是必需的,它就有可能被选为癌症基因,这可能会抵消传统的基于差异表达的方法在黑暗的基因揭示和缺失数据情况下的缺点。最后,对图中6338个基因进行加权。图的拓扑结构与原蛋白质相互作用网络保持一致。

实验和评价

整个实验过程如图所示。1

图1
图1

实验流程图。红色、蓝色和绿色线分别对应WMFVS、WFVS和随机MFVS管道

首先,我们分析了人类蛋白质与传统MFVSs的定向相互作用网络,得到了一组463个顶点。然后,我们在同一网络上使用我们的WMFVS方法(权值由FC值得到)。我们还使用权重的倒数作为惩罚值,并将其应用到我们的WFVS方法中。

因为MFVS方法的非唯一性的,它不是一个总体评价,如果我们只考虑一个MFVS结果。因此,我们通过应用WMFVS方法与随机洗牌基因重量计算一组随机MFVSs的。首先,我们计划来计算分析1000个随机MFVSs。However, since the Gurobi optimizer (version 8.1.0) does not always output a real optimal solution (e.g., even when we restrict the size of the output to be exactly 463, which is the size of the MFVS, sometimes the sizes of the output are smaller than 463), we filtered the obviously incorrect results and verified all the other outputs as MFVSs. Finally, we obtained 875 approved random MFVSs (since some MFVSs may be lost in theignore_w操作和MFVSs不是均匀分布的,并不是所有可能的MFVSs具有相同的随机选择的可能性)。

WMFVS和WFVS结果数据可在补充数据中找到。随机MFVS数据放置在https://github.com/lrming1993/WMFVS_codes.

为了评估这三种方法的结果,我们首先检查图级结果(见表)2).

表2每种方法的图形级结果

MFVS的运行时间是由于使用了传统的非加权MFVS方法。MFVS的权重总和使用875个随机加权wmfvs的平均值。

正如我们所预料的,WMFVS方法比传统的MFVS获得了更好的总权值。然而,WMFVS的结果并不总是优于MFVS。传统MFVS方法输出的总权值是随机的(输出与图结构相关,但与顶点权值无关),因此MFVS可以输出高权值的顶点集,甚至高于计算的WMFVS的权重(Gurobi可能并不总是给出一个真正的最优结果,因为其数值不稳定)。然而,我们的WMFVS方法显然具有更好的稳定性。

WFVS方法返回一个有528个顶点的FVS,比MFVS的大小大约大14%。所选的WFVS比MFVS和WMFVS具有更好的平均权重。这个结果与我们对wfvs的目的是一致的,我们关注的是总重量而不是FVS的大小。

然后,我们使用5个制备的癌症相关基因数据集来评估这三种方法的结果。我们在5个数据集上验证了3种FVS方法的召回率。结果如表所示3.和无花果。2

图2
figure2

随机mfvs(箱线图)、WMFVS方法(橙色圈)和WFVS方法(青色圈)在不同癌症基因数据集上的召回分布

表3各方法在不同基因集的查全率

我们可以看到,WMFVS和WFVS比在所有五集,这是明确定义的基因权重的好处(尤其是WFVS)传统MFVS更好的召回。此外,我们计算WMFVS和WFVS为875个随机MFVSs(表的p值4).

表4随机mfvs的WMFVS和WFVS的p值

对于某一数据集,用表示WMFVS的查全率\(r_ {wmfvs} \).所有随机mfvs的召回组成一个集合\(R_ {随机} \).然后通过以下公式计算WMFVS的p值:

$ $ \{对齐}开始p_ {WMFVS} = \压裂{| \ {| R \通用电气R_ {WMFVS},在R_ R \{随机}\}|}{| R_{随机}|}\{对齐}$ $
(2)

WFV的p值的计算与上述相同。

接下来,作为对照方法,我们考虑了几种其他癌症基因预测方法。

  1. (1)

    随机选择463个基因(选择100次,取平均值性能)。

  2. (2)

    选择权重最高的463个基因,这是一种传统的基于差异表达的方法。

  3. (3)

    选择至少49.5%MFVS的基因组(我们使用49.5%,因为基因的数量恰好是463)。

方法(2)只使用权重进行分类(即纯微分表达式分析方法),而方法(3)只使用图论结果(即纯网络分析方法)。方法(3)选择出现在MFVS中最常见的基因。直观地说,这些基因在图的拓扑结构中应该具有重要的意义。表中列出了所有这些方法的召回和精度5.此外,见图。3.

图3
图3

所有方法的召回和精确

图4
图4

每个数据集的浓缩分数

表5所有方法的召回(和精度)

讨论

绩效和充实分数

在ONGene,TSGene和MSigDB,WMFVS和WFVS均具有良好的p值,但对于CGC和NCG,p值是比较高的。一个主要的原因是,存在所述数据集的分类度量和所定义的基因重量之间的一些相关性。为了分析这种相关性,我们利用从GSEA [富集分数(ES)25.,它反映了一个集合的程度年代在整个排名列表中,极端(顶部或底部)的比例过高。

首先,我们根据权重从高到低对网络中的所有基因进行排序。然后,对于特定的癌症基因组年代,我们遍历已排序的基因列表,当我们遇到一个基因时,增加一个累加的统计量年代当我们遇到不存在的基因时就减少它年代.我们修改增量和减量值,以确保基因序列末尾的运行和为0。5个数据集的富集分数如图所示。4

很容易看到ONGene, TSGene和MSigDB数据集在列表的顶部显著丰富。虽然NCG在排行榜顶端似乎很富有,但它的ES相对较低;CGC的ES比NCG更差。最丰富的数据集是MSigDB。由于该数据集是直接从微阵列癌基因微扰的基因表达数据构建的,因此它与差异表达值密切相关。ES值解释了WMFVS和WFVS在不同数据集上的不同性能。

表格5和无花果。3.结果表明,除了在MSigDB中,WMFVS具有最好的精度和最好的召回率。在MSigDB中,癌基因与乳腺癌基因的差异表达值密切相关,简单的基于权重的方法(即方法(2))的精度为87.5%。在这种情况下,网络结构的集成可能会降低精度。然而,在大多数情况下,很难找到如此紧密相关的分类指标。我们可以观察到,在其他数据集中,方法(2)的表现比其他方法差。结果支持我们的WMFVS和WFVS方法的有效性。

黑暗的基因

如前所述,传统的基于差异表达的方法无法发现差异表达值较低的图级重要基因,即暗基因。在我们的研究中,我们将暗基因定义为权重相对较低(即差异表达值较低)但在癌症基因数据库中被记录为癌症基因的基因。具体地说,我们首先使用的标准的差异表达基因(DEGs)(|\log _2 FC|\ ge1 \)和调整假定值\ (le 0.05 \ \)来自TCGA乳腺癌RNA-seq数据,其中足球俱乐部是某一基因的倍数变化值。基于这些标准,我们发现了4245个DEG(称为DEG集)。接下来,我们通过排除这些deg,从每个癌症基因数据集中筛选出黑暗基因集。

在我们的实验中,我们进一步选择权重最高的463个基因(即差异表达最多的基因;被称为top-463 DEG集),以避免与WMFVS和WFVS方法分别鉴定的WMFVSs和WFVSs的基因数量不平衡。对于每个癌症基因数据集,all-DEG集合、top-463 DEG集合、WMFVS和WFVS的精度如图所示。5

图5
图5

比较all-DEG集、top-463 DEG集、WMFVS集和WFVS集在5个不同癌症基因数据集中的精度。‘DG’和‘NDG’分别代表暗基因和非暗基因的比例。注意,所有的DEG和前463个DEG集不包含暗基因

数字5结果表明,在5个癌症基因数据集中的4个,我们的WMFVS和WFVS方法比传统的基于DEG的方法(即全DEG集和前463 DEG集)显示出更好的精度。此外,约60-70%的基因是暗基因,我们的WMFVS和WFVS方法检测到这些基因,而传统的DEG方法忽略了这些基因。即使是直接从微阵列数据或内部未发表的包含已知癌症基因干扰的分析实验中生成的MSigDB C6数据集,WMFVS和WFVS方法也有很好的检测暗基因的能力。综上所述,我们的WMFVS和WFVS方法在识别传统DEG方法难以发现的暗基因方面具有优势。

缺失数据情况下

在本研究中,为了保留网络的拓扑结构,减肥基因被分配0的默认重量而不是被移除。By further analysis, we found 3 weight-loss genes (i.e., CDC2, ZBTB8 and TADA3L) included in the WMFVS result, 7 weight-loss genes (i.e., CDC2, ZBTB8, RhoGDI, TADA3L, RNF12, NP and MAP3K7IP1) contained in at least one of the 875 random MFVS results, and no weight-loss genes in the WFVS result. In particular, CDC2 and ZBTB8 were included in all the random MFVS results as well as in the WMFVS result. The CDC2 gene is related to the highly conserved protein CDK1, which functions as a serine/threonine kinase and is a key player in cell cycle regulation [28.].CDC2基因也被认为是一种癌症相关基因,其过度表达可能在人类乳腺癌发生中发挥重要作用[29.].虽然关于ZBTB8基因少量,但相同的ZBTB家族蛋白ZBTB7A涉及癌组织和乳腺癌细胞系MDA-MB-231和MCF-7的高表达[30.,提示ZBTB8可能作为一个转录抑制因子或参与肿瘤发生。CDC2和ZBTB8基因的发现表明,WMFVS方法可能弥补了传统DEG方法在缺失数据案例中的不足。

结论

我们提出了几种癌症基因预测的新方法。我们的WMFVS方法使用差异基因表达来选择MFVSs,提高了通用MFVS算法的稳定性,并且在定义好基因权重的情况下获得了比基于差异基因表达的方法更好的结果。我们的WFVS方法是WMFVS的一种变体,其目的是在网络中找到包含最大总重量的FVS。与WMFV相比,该方法通过牺牲精确度获得了更好的召回率。因此,一般来说,如果研究人员想要揭示尽可能多的潜在癌症基因,WFVS更好;如果研究者更喜欢精确性,那么WMFVS就更好。此外,由于WFV忽略了输出大小的限制,因此它比WMFV更关注顶点权重。因此,如果研究人员对权重定义有很好的信心,即权重与分类密切相关,那么WFV将比WMFV有更好的结果。我们可以从对MsigDB数据集的数据分析中看到这一点,该数据集在我们定义的权重上具有最高的富集分数。然而,在许多情况下,由于我们不确定定义的权重是否与分类密切相关,因此使用WMFV将保持更好的预测精度。

WMFVS和WFVS利用了生物数据和网络结构。它们可以用于新的癌症基因预测和评估,同样的想法也可以应用于其他生物信息学问题。我们方法的主要挑战是权重的定义。当权重定义良好时,WMFVS和WFVS可以表现得很好,但当权重与类别不直接相关时,可能会显示有限的性能。另一个问题与图压缩有关。在我们的实验中,传统的MFVS方法对压缩图进行了分析忽略活动请参见下一节中的详细信息),其中包含660个顶点和5604个圆弧,它非常有效,只需大约4秒钟即可获得结果。WMFV和WFV的输入图使用有限的\(忽略\ _w \)操作(参见在下一节细节),其中载2348个顶点和17283个弧。因为不同的输入秤,WMFVS和WFVS不是那样有效的简单MFVS方法,虽然时间成本仍然是可接受的。新算法加权图压缩开发留作将来的工作。

方法

图像压缩

在生物网络中,网络通常包含数万个顶点和数十万个弧。在许多情况下,由于MFVS问题的NP硬度,处理大网络是不实际的[12.].通常,我们可以将原始图压缩成一个更简单的图,以保持(或恢复)原始图的MFVS的大小。

在以下部分中,我们将定义v成功v精准医疗作为顶点的继承人和前辈v, 分别。让\(v_i \)成为网络中的一个顶点年代.考虑以下三种情况[18.]:

  1. C1。

    在v_i.suc \ (v_i \ \),也就是说,\(v_i \)有自身环;然后,\(v_i \)应该在所有fvs中,否则自循环不能被删除。

  2. C2。

    \ (v_i.suc = \ emptyset \)(或\(v_i.pre = \ emptyset \));然后,\(v_i \)不在任何MFVS中,因为它不在任何周期中。

  3. C3。

    \(| v_i.suc | = 1 \)(或\(| v_i.pre | = 1 \));让\ (v_j \)是唯一的继任者(或前身)\(v_i \);然后,任何包含的循环\(v_i \)还包含\ (v_j \)

对于C1,我们使用临时列表\(δM \ \)记录\(v_i \);我们添加\(v_i \)\(δM \ \)和删除\(v_i \)以及它所有的进出弧线。我们使用\(删除(V_I)\)表示这种去除过程。

对于C2,自\(v_i \)是不是在任何MFVS,我们可以安全使用\(删除(V_I)\)没有对可能的mfvs进行任何更改。

C3,假设\(v_i \)处于某种循环中c.如果我们试图打破c通过删除\(v_i \),那么移除同样好(有时更好)\ (v_j \)而不是\(v_i \).在这里,我们连接所有的前辈\(v_i \)到所有的继任者然后使用\(删除(V_I)\).这个连接和移除操作用\(忽略(v_i, S) \),在那里年代当前的图表是哪个\(v_i \)属于。该程序如下:

人物

在上述程序中,v图中的顶点是什么年代,年代E是一组图表年代.然后我们有以下程序来压缩一个图年代

图B

我们重复这个过程,直到年代无法修改。

此外,我们使用强连接组件(scc) [17.19.缩小弧线。由于两个scc之间的弧不在任何循环中,删除这些弧不会改变任何mfvs。我们使用\(压缩\ _scc (S) \)表示删除两个不同scc之间的所有弧的操作年代.整个图形压缩过程如下:

图

返回的\(δM \ \)包含总是在任何MFVS中的顶点和的并集\(δM \ \)压缩图的任何MFVS都将是原始图的MFVS。

请注意,并非原始图形的所有MFVSs都可以通过上述方法获得。某些MFVSs在中丢失忽略操作,而在加权MFVS问题中,丢失的MFVS可能具有最大权重。对于加权的情况,我们修改忽略运算来考虑顶点的权值(仅适用于正权情况)。以下方法可以确保最大权重MFVS (WMFVS)不会丢失:

算

在哪里vw为顶点的权值v

定理1

当顶点的重量是正的时,顶点忽略了\(忽略\ _w \)程序不在任何WMFVS中。

证明

假设\ (v.pre = \ {v ' \} \)\(v.w ,v属于WMFVS.然后,\(v'\n不在M\),否则\(m':= m - \ {v \} \)仍然是FVS,其顶点数少于MFV。

现在考虑\ (M”:= (M - \ {v \}) \杯\ {v ' \} \).很明显\ \ (M”)是MFVS。自从\ (v ' .w > v.w \),我们有Sigma _{v_i \in M} v_i。w< \Sigma _{v_j \in M''} v_j.w.\)因此,不能是WMFVS,即,如果v只有一个前身和v比前任的少吗v不属于任何WMFVS。

证明是类似的v只有一个继承人和重量v比后继者少。\广场(\ \)

MFVS和WMFVS的ILP配方

压缩过程结束后,如果压缩图不为空,可以使用ILP方法[17.]来解决剩下的MFVS问题。对于每个剩余的顶点\(v_i \),我们添加两个参数\ (x_i \)(布尔),\ (k_i \)(整数)\ (x_i \)表示是否\(v_i \)是否包含在输出MFVS结果中\ (k_i \)是ILP中使用的临时参数。ILP公式如下:

ILP1:

数组$ $ \开始{}{* c {20}} \ textbf{最小化}& \σx_i \ \ \ textbf{受制于}& k_i-k_j + nx_i \通用电气1 \:给所有在E (v_i, v_j) \ \ \ \ & \ textbf{哪里}\:0 \ le k_i \ le n - 1 \: \ textbf{和}\:x_i \: \ textbf{是布尔}\{数组}$ $

在哪里E为剩余图的弧集。

这些约束可确保选定顶点构成的FV为年代,而目标函数表示所选择的FVS具有最小尺寸,即为MFVS。

现在我们考虑MFVS问题的加权情况。给定一个图年代,每个顶点在哪里在S.V \ (v_i \ \)有一个重量\ (v_i.w \)(在下文中,我们用\ (w_i \)表示\ (v_i.w \)如果没有歧义),WMFVS问题是找到的MFVS年代它有最大的总重量。假设我们已经知道了大小年代(通过ILP1或某些估计方法,如[31.] 或者 [32.]),以下配方优化选定的MFVS为WMFVS:

ILP2:

$$\begin{array}{*{20}c}\textbf{Maximize}&\Sigma w_i x_i\\\textbf{Subject to}&\Sigma x_i=s\\\&k_i-k_j+nx_i\ge 1\\:对于所有(v_i,v_j)\in E\\\\\&\textbf{where}:0\le k_i\le n-1\\:\textbf{$$

约束\ (\ x_i = s \)确保所选择的FVS为MFVS,而目标函数在所有可能的MFVS中选择权重最大的MFVS。

最大重量阵线

在WMFVS问题中,我们首先将FVS的大小限制为最小,然后选择权值最大的MFVS作为目标。然而,有时重量可能比FVS的大小更重要。例如,在图中。6, WMFVS是\ (\ \ {b} \),总重量为\ (-20 \).如果我们不限制集合的最小大小,即FVS\(\{a,c\}\),它有重量\ [4 \),似乎更好。

图6
图6

一个简单的例子。在这种情况下,总重量可能比FVS的大小更重要

在这里,我们定义了WMFV的变体问题,它忽略了输出顶点集的精确大小,如下所示:给定图形年代,每个顶点在哪里在S.V \ (v_i \ \)有一个重量\ (v_i.w \)(或\ (w_i \)),加权FVS (WFVS)问题是寻找一个FVS年代它有最大的总重量。我们可以简单地使用与ILP2类似的ILP来解决WFVS问题。

ILP3:

$$ \ begin {array} {* {20} c} \ textbf {maximize}&\ sigma w_i x_i \\ \ textbf {textbf {textbf {textbf {textbf}&k_i-k_j + nx_i \ ge 1 \:\ forall(v_i,v_j)\在e \\&\ textbf {where} \:0 \ le k_i \ le n-1 \:\ textbf {and} \:x_i \:\ textbf {是\,boolean} \ end {array} $$

然而,简单地移除约束\ (\ x_i = s \)当顶点的权值为正时,可能会得到一个平凡解,因为所有顶点的集合总是一个WFVS。这里我们考虑两种方法来避免平凡解:

  1. 1。

    修改所有权重为负。假设顶点的最大权重为\ (w_m \);然后,对于每个重量\ (w_i \),将其修改为\ (w_i:ε= w_i-w_m - \ \).在这里,\ε(\ \)是一个小的正数,以确保所有的权重为负。该ILP是一样的ILP3。

  2. 2。

    将权重反转为惩罚值。我们可以通过求它们的倒数来做\ (w_i \),也就是说,

    $$ \ {开始对准} P_I = \左\ {\开始{阵列} {LL} \压裂{1} {w_i}和{} \ {mathbf如果} \,w_i \ NE 0 \\ \ infty&{}\ mathbf {如果} \,w_i = 0 \ {端阵列} \右。\结束{对齐} $$

    将ILP3公式修改如下:ILP3”:

    数组$ $ \开始{}{* c {20}} \ textbf{最小化}& \σp_i x_i \ \ \ textbf{受制于}& k_i-k_j + nx_i \通用电气1 \:给所有在E (v_i, v_j) \ \ \ \ & \ textbf{哪里}\:0 \ le k_i \ le n - 1 \: \ textbf{和}\:x_i \: \ textbf{\,布尔}\{数组}$ $

在我们的研究中,我们检验了WFVS方法中计算权重的两种方法。我们发现第一次修改在运行ILP过程时更加不稳定,即ILP结果出现的错误更加明显。因此,在WFVS方法中,我们选择使用第二种方法来计算权重;也就是说,我们将权重反转为惩罚值,惩罚值总是正的。

在第二种方法中,我们需要避免“被零除”的错误。为此,我们使用下面的简单启发式公式。

l是一个大的数(在我们的程序中,我们使用65536);然后,惩罚计算为:

$$\begin{aligned}p\u i=\left\{\begin{array}{ll}\frac{1}{w{u i}&{}\mathbf{if}\,w\u i\ge\frac{1}{l}\\l&{mathbf{if}\,w\u i<\frac{1}{l}\end{array}\right\结束{对齐}$$

实验环境

我们使用英特尔(R)核心(TM)I7-7700 CPU和32.0 GB RAM在Python 3.7.0中实现了所有方法。这compress_scc程序使用Gabow算法[33.].ILP处理基于Gurobi 8.1.0 [34.].

数据和材料的可用性

源代码在GitHub上(https://github.com/lrming1993/WMFVS_codes). 随机MFVS结果也可以在这个URL上找到。本研究中产生的所有数据均包含在本文及其补充信息文件中。

缩写

MFVS:

最小反馈顶点集

WMFV:

加权最小反馈顶点集

WFVS:

最大加权反馈顶点集

独立:

整数线性规划

舰队指挥官:

折叠变化

锿:

丰富分数

鳞状细胞癌:

强连通分量

度:

差异表达基因

参考

  1. 1。

    Vogt PK,癌症基因。中华医学杂志。1993;158(3):273-8。

    中科院PubMed公共医学中心谷歌学者

  2. 2。

    罗鹏,丁勇,雷旭,吴凤霞。deepDriver:利用深度卷积神经网络基于体细胞突变预测癌症驱动基因。麝猫。2019;13。

    中科院文章谷歌学者

  3. 3。

    Tokheim CJ, Papadopoulos N, Kinzler KW, Vogelstein B, Karchin R.评估癌症驱动基因的评估。中国科学院院刊。2016;113(50):14330-5。

    中科院文章谷歌学者

  4. 4.

    王志强,王志强,王志强,等。癌症基因组体突变研究的设计与分析。基因组学,2009;93(1):17。

    中科院文章谷歌学者

  5. 5.

    程飞,赵建军,赵志军。癌症基因组驱动突变和显著突变基因优先排序方法的研究进展。简报Bioinf。2016;17(4):642 - 56。

    中科院文章谷歌学者

  6. 6.

    戴华,李丽,曾涛,陈立林。基于RNA测序数据构建细胞特异性网络。核酸学报2019;47(11):62-62。

    文章谷歌学者

  7. 7.

    Ebbert MT, Jensen TD, Jansen-West K, Sens JP, Reddy JS, Ridge PG, Kauwe JS, Belzil V, Pregent L, Carrasquillo MM,等。对暗基因和伪装基因的系统分析揭示了隐藏在普通人群中的疾病相关基因。基因组医学杂志。2019;20(1):97。

    文章谷歌学者

  8. 8.

    杨国强,杨国强。基于非线性动力学的复杂网络结构控制。Zañudo中国科学院院刊。2017;114(28):7234-9。

    文章谷歌学者

  9. 9.

    Mochizuki A, Fiedler B, Kurosawa G, Saito D.反馈顶点集的动力学与控制。II:用于确定调控网络中分子活性多样性的可靠监视器。J Theor Biol. 2013; 335:130-46。

    文章谷歌学者

  10. 10。

    郭WF,张SW,刘LL,刘楼石QQ,张立,唐Y,曾T,在癌症单一样品通过网络控制策略的陈L.情迷个性化的驱动程序突变谱。生物信息学。2018; 34(11):1893-903。

    中科院文章谷歌学者

  11. 11.

    基于反馈顶点集的有向复杂网络控制的临界顶点和冗余顶点分析。中国生物医学工程学报。2018;25(10):1071-90。

    中科院文章谷歌学者

  12. 12.

    gary MR, Johnson DS。电脑和棘手。旧金山:弗里曼;1979.

    谷歌学者

  13. 13。

    有界周期反馈顶点集的不可逼近性。见:计算复杂性电子研讨会(ECCC),第21卷;2014.2页。

  14. 14.

    李志强,李志强,李志强,等。一种求解环割集问题的随机算法。J Artif Intell Res. 2000; 12:219-34。

    文章谷歌学者

  15. 15.

    曹勇,陈杰,刘永强。反馈顶点集的新测度和新结构。Algorithmica。2015;73(1):63 - 86。

    文章谷歌学者

  16. 16.

    利用最小三角法寻找诱导子图。2009.arXiv预印本arXiv: 0909.5278

  17. 17.

    Chakradhar ST, Balakrishnan A, Agrawal VD。一种选择局部扫描触发器的精确算法。电子学报。1995;7(1-2):83-93。

    文章谷歌学者

  18. 18.

    王传忠。基于最小反馈顶点集的求解方法。计算机系统科学。1988;37(3):292-311。

    文章谷歌学者

  19. 19.

    Smith G,Walford R.识别定向图的最小反馈顶点组。IEEE Trans Circuits Syst。1975; 22(1):9-15。

    文章谷歌学者

  20. 20.

    Vinayagam A,Stelzl U,Foulle R,Plassmann S,Zenkner男,蒂姆Ĵ,Assmus HE,安德拉德-纳瓦罗MA,Wanker EE。有向蛋白相互作用网络调查的细胞内信号转导。科学信令。2011; 4(189):8-8。

    文章谷歌学者

  21. 21。

    ONGene:基于文献的人类致癌基因数据库。中国基因工程杂志。2017;44(2):119-21。

    文章谷歌学者

  22. 22。

    赵M,Sun J,Zhao Z. Tsgene:肿瘤抑制基因的网页资源。核酸RES。2013; 41(D1):970-6。

    文章谷歌学者

  23. 23。

    Sondka Z, Bamford S, Cole CG, Ward SA, Dunham I, Forbes SA。宇宙癌症基因普查:描述所有人类癌症的基因功能障碍。2018;18(11): 696-705。

    中科院文章谷歌学者

  24. 24。

    Repana d,NulsenĴ,德雷斯勒L,Bortolomeazzi男,文卡塔SK,Tourna A,雅克夫勒维A,Palmieri的T,Ciccarelli FD。肿瘤基因网络(NCG):从癌症测序屏幕知和候选癌症基因的综合目录。基因组Biol。2019; 20(1):1。

    文章谷歌学者

  25. 25。

    Subramanian A, Tamayo P, Mootha VK, Mukherjee S, Ebert BL, Gillette MA, Paulovich A, Pomeroy SL, Golub TR, Lander ES等。基因集富集分析:一种解释全基因组表达谱的基于知识的方法。中国科学院院刊。2005;102(43):15545-50。

    中科院文章谷歌学者

  26. 26.

    Weinstein JN, Collisson EA, Mills GB, Shaw KRM, Ozenberger BA, Ellrott K, Shmulevich I, Sander C, Stuart JM, Network CGAR等。癌症基因组图谱泛癌症分析计划。Nat麝猫。2013;45(10):1113。

    文章谷歌学者

  27. 27.

    林超英,李昌华,庄永华,李建勇,赵洋洋,李永华,钟永杰,黄家杰,黄树华,陈丽玲,等。跨人类癌症的膜蛋白调控网络。Nat Commun。2019;10(1):17。

    文章谷歌学者

  28. 28.

    摩根。细胞周期:控制原则。伦敦:新科学出版社;2007.

    谷歌学者

  29. 29.

    蔡SW, Sohn JH, Kim D-H, Choi YJ, Park YL, Kim K, Cho YH, Pyo J-S, Kim JH。人乳腺癌中Cyclin B1, cdc2, p16和p53的过表达:临床病理相关性和预后意义。延世医学2011;52(3):445-53。

    文章谷歌学者

  30. 30.

    毛A,陈M,秦Q,梁Z,江W,杨W,魏C。ZBTB7A通过NF促进人乳腺癌细胞的迁移、侵袭和转移-\ (\ kappa \)b诱导的体外和体内上皮-间充质转化。。2019;166(6):485 - 93。

    中科院文章谷歌学者

  31. 31.

    江W,刘T,仁T,徐K。两种硬度对反馈顶点集的结果。在:信息和管理中的算法和算法方面的前沿。柏林:斯普林克;2011.第233-243页

  32. 32.

    Madelaine FR, Stewart IA。改进了网格和蝴蝶反馈顶点数的上界和下界。离散数学。2008;308(18):4144 - 64。

    文章谷歌学者

  33. 33。

    Gabow HN。基于路径的深度优先搜索强和双连接组件。Inf Process Lett. 2000; 74:107-14。

    文章谷歌学者

  34. 34。

    L. Gurobi优化参考手册(2020)。http://www.gurobi.com

下载参考资料

确认

不适用。

资金

这项工作得到了(1)日本京都大学化学研究所国际合作研究计划的部分支持;(2)科技部青年学者资助项目(科技部资助项目MOST 109-2636-B-009-007);(3)智能药物系统与智能生物器件研究中心\ (^ 2 \)B)教育部高等教育萌芽项目(HESP),台湾;(4)教育部特色领域研究中心项目“面向治疗发展的动态系统生物学智能平台”;(5)国家自然科学基金项目(62002329);(6)河南省重点科技项目(212102310083);(7) 2020年河南博士后科研启动项目;(8)郑州大学顶级博士科研启动经费(32211739)。资助机构在研究的设计、数据的收集、分析和解释以及手稿的撰写中没有发挥任何作用。

作者信息

从属关系

作者

贡献

TA和CL构思和设计了这项研究。TA和RL设计了算法。RL、CL和WG准备了实验数据。RL执行所有的实现和结果分析。RL制作了初稿。所有作者都参与了最终定稿,并通过了提交的草稿。

相应的作者

对应到大同

伦理宣言

伦理批准和同意参与

不适用。

同意出版

不适用。

相互竞争的利益

TA是BMC生物信息学的副主编。欧宝娱乐合法吗

补充资料

出版商的注意

欧宝体育黑玩家施普林格《自然》杂志对已出版的地图和机构附属机构的管辖权要求保持中立。

补充信息

额外的文件1。

.压缩网络的边缘数据;的忽略采用手术治疗。该文件用于传统的MFVS计算。

附加文件2。

压缩网络的边缘的数据;两者都不忽略也不ignore_w是使用。该文件用于WFVS计算。

额外的文件3。

压缩网络的边缘数据;的ignore_w使用过程。该文件用于WMFVS计算。

附加文件4。

网络中所有基因的权重。

附加文件5。

这个∆从过程3计算,其中忽略操作使用。当使用附加文件1计算MFVS时,此文件是必需的。

额外的文件6。

这个∆从过程3计算,其中ignore_w操作使用。使用其他文件3计算WMFV时,此文件是必需的。

额外的文件7。

传统MFVS方法的结果。

额外的文件8。

WMFVS方法的结果。

额外的文件9。

WFVS方法的结果。

权利和权限

开放访问本文是基于知识共享署名4.0国际许可,允许使用、共享、适应、分布和繁殖在任何媒介或格式,只要你给予适当的信贷原始作者(年代)和来源,提供一个链接到创作共用许可证,并指出如果变化。本文中的图像或其他第三方材料都包含在本文的知识共享许可中,除非在该材料的信用额度中另有说明。如果资料不包括在文章的知识共享许可协议中,并且你的预期用途没有被法律规定允许或超过允许用途,你将需要直接从版权所有者获得许可。如欲查阅本许可证副本,请浏览http://creativecommons.org/licenses/by/4.0/.Creative Commons公共领域奉献豁免(http://creativecommons.org/publicdomain/zero/1.0/)适用于本文中提供的数据,除非另有用入数据的信用额度。

再版和权限

关于这篇文章

通过CrossMark验证货币和真实性

引用这篇文章

李,R.,林,CY。,Guo,WF。et al。加权最小反馈顶点集及其在人类癌症基因检测中的实现。欧宝娱乐合法吗22,143(2021)。https://doi.org/10.1186/s12859-021-04062-2

下载引用

关键字

  • 反馈点集
  • 差异基因表达
  • 癌症基因