The Bioinformatics Lab
Probabilistic Networks Alignment
Interactions between molecules are probabilistic events. An
interaction may or may not happen with some probability, depending
on a variety of factors such as the size, abundance or proximity of
the interacting molecules. In this paper we consider the problem of
aligning two biological networks. Unlike existing methods, we allow
one of the two networks to contain probabilistic interactions.
Allowing interaction probabilities makes the alignment more
biologically relevant at the expense of explosive growth in the
number of alternative topologies that may arise from different
subsets of interactions that take place. We develop a novel method
that efficiently and precisely characterizes this massive search
space. We represent the topological similarity between pairs of
aligned molecules (i.e., proteins) with the help of random variables
and compute their expected values. We validate our method showing
that, without sacrificing the running time performance, it can
produce novel alignments. Our results also demonstrate that our
method identifies biologically meaningful mappings under a
comprehensive set of criteria used in the literature as well as the
statistical coherence measure that we developed to analyze the
statistical significance of the similarity of the functions of the
aligned protein pairs.
Keywords: probabilistic biological
networks, network alignment, neighborhood topology, random graphs
Download the entire protein interaction networks of the organisms
used in this paper and their pairwise alignment results.
Download the small subnetworks generated for this paper. The
subnetworks are obtained by partitioning the entire MINT protein
interaction networks of various organisms based on the pathway they
belong to in the KEGG database.
Download the list of all KEGG pathways used in this paper.
Download the software for aligning pairs of networks based on
the algorithm described in this paper.
- Andrei Todor
- Alin Dobra
- Tamer Kahveci
- Andrei Todor, Alin Dobra, Tamer Kahveci.
Probabilistic Biological Network Alignment,
Transactions on Computational Biology and Bioinformatics Journal
(IEEE/ACM TCBB). in press.
Last modified: Wed Mar 6 15:57:46 EST 2013