论文部分内容阅读
不断发展的生物实验测定技术产生了越来越多的生物网络数据，比如蛋白质相互作用网络、基因转录调控网络等，这些数据中蕴含了大量的关于各种有机体之间相互影响和相互作用关系的信息。如何解释和分析此类生物网络数据，已经成为当前生物信息学领域的一个亟待解决的问题。其中，有一类重要的研究工作就是生物网络数据的比较，即生物网络比对。生物网络比对，简言之就是要寻找两个（或多个）生物网络顶点之间的一组映射关系，使得生物网络之间的相似性得分最高。 值得注意的是，由于一些原因，比如生物网络中相互作用模块的规模、密度、冗余度以及模块间的距离，甚至生物实验的误差，都会导致测量得到的数据不完全准确，使得其中含有许多不确定事件（概率事件），比如蛋白质相互作用网络中的边是以一定概率存在的，基因转录调控网络中的DNA也是以一定概率被转录成为RNA的。因此，在生物网络比对过程中，充分考虑和利用不确定信息，使用不确定图结构刻画原始网络，可以更准确地对现实情况进行建模，从而得到更准确的比对结果。然而，由于不确定图的概率特性，这些不确定信息在提高比对结果准确性的同时，也提高了算法的复杂度。目前绝大多数的生物网络比对算法都是针对确定生物网络比对问题而设计的，仅有极少数的算法可以处理不确定生物网络数据。因此，本论文针对不确定生物网络比对进行了研究，主要工作包括: 1、本文提出了一种改进的不确定生物网络比对算法PBNA(Probabilistic BiologicalNetwork Alignment)。在确定生物网络比对算法IsoRank的基本框架之上，PBNA将不确定生物网络信息纳入到顶点相似性矩阵构建过程中，允许参与比对的两个网络中有一个为不确定网络，之后应用邻居二分图(NBG)和贡献者(Contributor)改进了相似性矩阵计算公式，从而提高了顶点相似性计算的精度，并应用概率母函数降低了求解矩阵内每个元素期望的复杂度。实验验证了PBNA能够得到现有的确定生物网络比对算法得不到的比对结果，并以我们所知的现存唯一的不确定比对算法Prob为参考标准，验证了PBNA可以在更短的时间内得到更具生物意义的比对结果。 2、现有的Prob算法和PBNA算法仅能够利用到一个生物网络中的不确定信息，即只允许参与比对的两个网络其中一个是不确定网络。因此，本文进一步提出了“完全的不确定网络比对(Complete Probabilistic Alignment)”概念，并将现有的Prob算法与PBNA算法分别改进为完全不确定比对算法Prob CP与PBNA CP。两种改进的算法分别在原算法的基础之上，将之前被忽略掉的一个网络中的不确定信息纳入到顶点相似性矩阵构建过程中，并利用离散随机变量相关理论求其期望值，参与之后的运算。实验结果验证了两种扩展算法的有效性，并比较了二者的生物意义和时间效率，再次验证了加入Contributor等概念的PBNA_CP算法能够得到更具生物意义的比对结果，以及有着更高的时间效率。