Page 25 - 《软件学报》2020年第11期

刘中舟 等:动态基因调控网演化分析 3341

性代表着一个点在图中作为中心节点的地位.
(3) 模体个数.对一个有向边(u,v),考虑将包含了(u,v)的模体个数作为其特征.设该模体的第 3 个节点为 w.
若该模体中存在有向边(u,w),则称此边为前向边(F),若存在有向边(w,u)则称此边为后向边(B),或者 w
和 u 之间没有边存在,则记为 N.w 和另一个节点 v 的关系同理.这样,对于一条边(u,v)有 8 个特征,分别
为 f FF ,f FB ,f BF ,f BB ,f FN ,f NF ,f BN ,f NB .
(4) 共同邻居.对一个有向边(u,v),如果存在另一个节点 w,使得 w 与 u 和 v 之间均有边相连,则 w 为 u,v 的
共同邻居.f cn (u,v)指有向边(u,v)的两端点的共同邻居的个数.
以上的显式特征是非常直观的,但基因调控网的网络演化规律十分复杂,仅使用以上特征无法很好地对基
因调控网的符号进行准确的判别.为了更好地利用源网络中已知符号的边所蕴含的信息,本文还构造了隐空间
特征以捕捉蕴藏在拓扑结构之下的源网络和目标网络之间共有的模式.
2.3.2 隐空间特征提取
通过 MT 算法,可以得到源网络 G s 以及目标网络 G t 的邻接矩阵 A s 和 A t .使用非负矩阵三因子分解将这两
组邻接矩阵在同一特征空间中进行因式矩阵分解,得到源网络和目标网络中边的隐空间特征.
非负矩阵三因子分解是非负矩阵分解的衍生,它的非负性和对稀疏矩阵的控制,可以有效地刻画数据中潜
藏的局部属性,并进行细粒度的特征提取.传统的非负矩阵分解用于将一个矩阵分解为两个非负矩阵的乘积,其
T
可以描述如下:给定矩阵 Z ∈ R + nm× ,寻找非负矩阵 H ∈ R + nr× 和非负矩阵 D ∈ R + mr× ,使得 Z≈HD .Ding 等人 [32] 在此基
T
础上引入了第 3 个因子,以调和 Z,H,D 之间可能存在的尺度上的不平衡,将问题重新描述为 Z≈HND ,其中,
H ∈ R + nk× ,N ∈ R k l× + ,D∈ R n l× + .基于非负矩阵三因子分解,本文将寻找隐特征空间的问题表示如公式(4)所示.
min J = A − ||U Σ V T || + 2 A − ||U Σ V T || + 2 α || Σ || ⎫
2
s s k s F t t k t F k F ⎪
s.t. ∑ k U sj ⋅ () = 1, ∑ k V sj ⋅ () = 1, ∑ k U t ( ) j ⋅ = 1, ∑ k V t () j ⋅ = 1 ⎪ ⎬ (4)
j= 1 j= 1 j= 1 j= 1 ⎪
×
,,U
UV s t ,V ∈ R + Mk ⎪ ⎭
t
s
||⋅|| F 为弗罗贝尼乌斯范数,M 为基因调控网规模.公式(4)的目标是寻找合适的矩阵分解,使 A ≈ U Σ k s T
V 且
s
s
A ≈ U Σ k t T k R + kk× 是源网络和目标网络共有的特征空间,两个网络所提取出的特征都在同一个特征空
V .矩阵 Σ ∈
t
t
间中表达.U s ,V s ,U t ,V t 是提取出的 4 个隐空间特征矩阵:U s 的第 i 行代表源网络第 i 个节点作为边的出节点的特
征向量,V s 的第 i 行代表源网络第 i 个节点作为边的入节点的特征向量,U t ,V t 同理.α为正则化系数.由于上式所有
变量都非负,在求最小值的过程中,Σ k 中过大的值将会使 U s ,V s ,U t 以及 V t 中的某些值趋于 0,这会使网络中每个
节点的隐空间特征向量难以区分.因此,需要加上一个正则项参数Σ k .
本文使用一种迭代更新的算法来求解上式.首先将上式改写成公式(5),便于用代码描述的形式.
V +
T
V +
V
J = tr (A A − s T s 2A U Σ k s T V Σ s k T U U Σ T s s k s T ) tr A A+ ( t T t 2A U Σ − T t t k t T V Σ t k T U U Σ T t t k t T ) α tr (Σ + k T Σ k ) (5)
V
s
s
其中,tr(⋅)是指矩阵的迹.以 U s 为例介绍求解上式的方法.由于约束条件中包含 U s ≥0,可以使用拉格朗日乘子法
解决此问题.本文引入拉格朗日乘子 L U s ∈ M k× ,并使拉格朗日函数 (L U s ) = J − tr (L U s U s ) 最小.设∂L(U s )/∂U s =0,
V V Σ
与 KKT 条件联立 L U si (, )j U s (, )i j = 0 ,可得 (2AV Σ − ss k T 2U U Σ + T s s k s T s k T ) (, ) j U s i ( , ) j = 0 .
i
基于上式和文献[33]的方法,本文按公式(6)所示规则迭代更新 U s .
(AV Σ T )
i
U ← U ss k (, ) j (6)
si (, ) j s i ( , ) j (U Σ V V Σ T T )
i
s ks s k (, ) j
同理可得 V s ,U t ,V t 和Σ k 的迭代规则如公式(7)~公式(10)所示,
T
(AU Σ )
i
V ← V s s k (, ) j (7)
si (, ) j s i ( , ) j T T
(V Σ s k U U Σ s s k ) (, ) j
i