Topology-only Local Network Alignment, Part 1. Seeds: Large Exact Subgraph Isomorphisms Using a Deterministic Graphlet Index

Abstract

We introduce the first algorithm designed for
topology-only local graph matching (a.k.a. local network align-
ment or subgraph isomorphism). BLANT (Basic Local Alignment
of Network Topology) first creates a limited, high-specificity index
independently for each graph, containing connected k-node
induced subgraphs called k-graphlets, for k=6-15. The index
is constructed in a deterministic way such that, if significant
common network topology exists between two networks, their
indexes are likely to overlap. This is the key insight which allows
BLANT to discover alignments using only topological informa-
tion. To find perfect local alignments between two networks,
BLANT queries their indices for perfect k-graphlet matches.
We then perform limited expansion of these exact matches to
larger, highly similar alignments (S3 >= 0.95) of up to 150 node-
pairs. Unlike previous "local" alignments that rely on a pre-
processing via global network alignment-thus being limited to
finding locally similar regions embedded in the global similarity
structure- 50% of node our pairs differ from their "assigned"
global counterpart. These results compare favorably against the
baseline, a state-of-the-art local alignment algorithm which was
adapted to be topology-only. Such alignments are 3x larger and
differ 30% more (additive) more from the global alignment
than alignments of similar topological similarity (S3 >= 0.95)
discovered by the baseline. Just as BLAST uses exact k-mer
matches as seeds for local sequence alignment, our regions of
extremely high network similarity can then be used as seeds which
can be extended larger, less perfect local network alignments.