本文以蛋白蛋白相互作用为主要研究对象，提出了一个新的预测蛋白蛋白相互作用的算法，新的基于功能关联度的利用蛋白相互作用预测蛋白功能的算法，以及3字符LCWIS问题的时间复杂度为O(nlog logn)的算法。 首先，我们从理论上将PPI预测问题转化为最小带权集合覆盖问题(MWSC)，由于最小集合问题是NP—hard的，无法高效的找到精确解，凶此一般采用近似算法求解。较为常见的近似算法是贪婪算法，但是贪婪算法的近似度是对数级的。因此，我们提出了一种近似度为常数的启发式的近似算法。实验证明我们的算法确实能够改进原有算法的性能。 其次，我们提出了基于功能关联的数邻居法(FANC)预测蛋白功能，我们创新性的引入了功能关联度的概念，并且应用到蛋白功能预测中去。实验证明，我们的方法能有效挖掘功能之间的关联度信息，将关联度结合蛋白相互作用网络预测蛋白功能比传统方法更加准确真实的反应了细胞内部的工作机制，在预测准确率上也超过了传统方法。 此外，我们给出了3字符LCWIS(Longest Common Weakly Increasing Substring)问题的时间复杂度为O(nlog log n)，空间复杂度为O(n)的新的算法，我们的算法在时间空间复杂度两个方面都是当前最好的。该问题的研究对于LCS，LIS等经典问题都有理论意义和价值。