链接预测方法概览

xuanzhang

miRNA-Disease 关系预测方法总结(文中方法也可用于解决其他链接预测的问题)

PS：由于帖子中图片好像无法在指定位置正常显示，特，上 传图片排版较好的pdf作为附件，方便下载阅读。

本帖的目的：介绍一些常用的链接预测方法，这些方法都已应用在生物信息以及社会网络的链接预测工作中，本文主要关注在miRNA和疾病关系预测中前人使用过的方法。

介绍思路：将常用的链接方法大致分为两类，一类是基于相似性测量的；另一类是基于机器学习方法的；针对每一类中的方法，注意进行介绍（包括方法思想和代码的介绍）；涉及的方法有（1）Katz方法（2）Random Walk方法（3）分步的Random Walk  （4）Hetesim 方法等方法，之后会继续补充。

基础知识：

（1）由于大部分方法是基于数据网络的（network based methods），因此需要先介绍下基于网络方法的一些基本定义。简单的说，就是从网络的角度看待数据，使用数据。将数据点想像成网络中的点，数据与数据之间的关联想象成网络中的边。举个例子，我们下载到的RNA-Disease 关联数据，其中包含两种数据点若干（RNA和disease），把他们看做网络中的点；他们之间的关联看做网络中存在一条边连接两点。如下图，通常用矩阵存储网络数据。

file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg

对于我们需要解决的RNA-Disease关联预测，通常研究者会构建如下的数据网络，如图

file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image004.jpg

（2）上图左侧由三个数据网络构成，其中disease相似性网络和RNA相似性网络可由多种方法计算获得。disease相似性网络和RNA相似性网络与可靠，预测结果也会更好。

方法介绍：以下方法均应用在上文构建好的数据网络上

类一（基于相似性测量）：

（1）Katz方法

         思想：数路径条数，在网络中，从A点到B点产生的可达路径条数越多，两点产生关联的可能性就更大；同时，认为路径长度不同对链接产生的贡献就不同，越长的路径贡献越小(若A->B ，AB关联强；若A->C->B，AB关联次强），从而赋予不同长度路径不同的权值。

         图解：在完整路径中可能产生的不同长度的路径种类

   

file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image006.jpg

         MATLAB代码：

   

   

（2）Random Walk方法（随机游走）

         思想：选择一些种子节点（赋初值，且从该点出发），考虑从这些点随机的到达到其他可达点的概率，不断迭代计算，使概率值最终达到稳定状态，概率越大认为从种子节点到该点产生链接的可能性越大。

         MATLAB代码：

   

（3）分步的Random Walk

         思想：有点将katz方法和Random walk相结合的意思，在Random walk的基础上，不考虑达到稳态时的结果，仅考虑前几次迭代的结果（路径长度短贡献大）作为最终结果。

         MATLAB代码：修改Random walk方法的迭代次数即可

（4）Hetesim 方法

- - - - - -  未完待续

论文参考：

（1）Integrativeapproaches for predicting microRNA function and prioritizing disease-relatedmicroRNA using biological interaction networks, Briefings in bioinformatics, 17(2)(2016), 193–203

（2）Prediction and validation of disease genesusing HeteSim Scores, IEEE/ACM Transactions onComputational Biology and Bioinformatics

----------------------------------------------------------------------------附件的分割线--------------------------------------------------------------------------------------