Transcript Liu

GLOBAL SIMILARITY BETWEEN
MULTIPLE BIONETWORKS
Yunkai Liu
Computer Science Department
University of South Dakota
BACKGROUND
Just as the rapid disclosing of genomic data
enables the study of sequence conservation, the
growth of network quality and availability allows
us to ask similar questions at network level.
One challenging problem is the characterization of
similar patterns among multiple biological
networks. However, there is no definition of
similarity between networks that has been
agreed upon and efficient algorithms for
comparing dynamic bio-networks are limited.
GRAPH MODEL AND PREVIOUS WORKS
The growth of quality and availability of new
biotechnology allows us to simulate biological systems
with graph models. Generally speaking, nodes
represent biological units (e.g., proteins or genes); and
edges represent physical or chemical relationships.
Previous works: PHUNKEE (2007); Græmlin (2006);
NetworkBLAST (2004);
PURPOSE AND SIGNIFICANCE
The global similarity of multiple bio-networks,
such as anatomical networks, gene regulatory
network and protein interaction networks, are
expected to evaluate the overall topological
likeness among graphs.
Biological Applications:
 Topological structural study
 Evolution of bio networks
 Experimental data analysis
METHOD
Basic method: compare the adjacent matrices of
networks.
Challenges:
 Sequence sorting: The nodes are generally weighted by
different attributes; however, the occurrence of same nodes
in graphs greatly increase the complexity for finding the
maximal global similarities between two networks.
 Transitivity: Especially in functional networks, the
transitivity should be considered. Another reason is to allow
gaps in study.
 Global and Local similarity: The optimal solution of global
similarity may cause the ignorance of local conserved
subgraphs. The comparison of similar graphs may have
noises.
CURRENT AND FUTURE WORK
Currently, a research team, consisting of
researchers from Computer Science Dept and
Medical School, are developing software and
biological applications based on bionetwork
comparison.
We are also looking for collaborators.
Please contact, [email protected]