  BLAST is a standard tool in bioinformatics for creating local sequence
alignments using a "seed-and-extend" approach. Here we introduce an analogous
seed-and-extend algorithm that produces local network alignments: BLANT (Basic
Local Alignment of Network Topology). In Part 1, we introduced BLANT-seed,
which generates graphlet-based seeds using only topological information. Here,
in Part 2, we describe BLANT-extend, which "grows" seeds to larger local
alignments using only topological information. We allow the user to specify
bounds on several measures an alignment must satisfy, including the edge
density, edge commonality (i.e., aligned edges), and node-pair similarity if
such a measure is used; the latter allows the inclusion of sequence-based
similarity, if desired, as well as local topological constraints. BLANT-extend
is able to enumerate all possible alignments satisfying the bounds that can be
grown from each seed, within a specified CPU time or number of generated
alignments. While topology-driven local network alignment has a wide variety of
potential applications outside bioinformatics, here we focus on the alignment
of Protein-Protein Interaction (PPI) networks. We show that BLANT is capable of
finding large, high-quality local alignments when the networks are known to
have high topological similarity -- for example recovering hundreds of
orthologs between networks of the recent Integrated Interaction Database (IID).
Predictably, however, it performs less well when true topological similarity is
absent, as is the case in most current experimental PPI networks that are noisy
and have wide disparity in edge density which results in low common coverage.
