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

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.