Random walk with restart: A powerful network propagation algorithm in Bioinformatics field

摘要

Various problems in biomedicine can be formulated as a ranking problem, where a set of candidate components is ranked relatively based on a set of known components. The most popular problem in biomedicine is identification of disease-associated cellular components, where cellular components can be genes, proteins, microRNAs or other molecules. Besides that, a number of problems in pharmacology is also similar such as identification of drug-target interactions and prediction of novel drug-disease associations. They are all considered as ranking problems. Many computational methods have been proposed to these problems including machine learning-based and network-based ones. In which, machine learning-based methods usually approach those as binary classification problems, where an unknown association/interaction is predicted as “associate/interact” or “not associate/interact”. However, as abovementioned, those problems should be formulated as ranking problems since it is often in biomedicine and pharmacology that not observed association/interaction does not mean it does not exist. Meanwhile, network-based methods have been naturally approached those problems by ranking candidate associations/interactions relatively to a set of known ones. Among network-based methods, random walk with restart (RWR), a network propagation algorithm, has shown to be state-of-the-art one for those problems. Therefore, in this study, we are going to review usage of this algorithm for a number of problems in biomedicine and pharmacology.