BLANT: Basic Local Alignment of Network Topology, Part 1: Seeding local alignments with unambiguous 8-node graphlets
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, for Basic Local Alignment of Network Topology. This paper introduces BLANT-seed: given an input graph, BLANT-seed uses network topology alone to create a limited, high-specificity index of k-node induced subgraphs called k-graphlets (analogous to BLASTS's k-mers). The index is constructed so that, if significant common network topology exists between two graphs, their indexes are likely to overlap. BLANT-seed then queries the indexes of two networks to generate a list of common k-graphlets which, when paired, form a seed pair. Our companion paper (submitted elsewhere) describes BLANT-extend, which "grows" these seeds to larger local alignments, again using only topological information.
Code (0)
등록된 구현이 없습니다.
Tasks
SpecificitySimilar Papers 제목 키워드 기반
BLANT: Basic Local Alignment of Network Topology, Part 2: Topology-only Extension Beyond Graphlet Seeds
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…
CPUHigh-Order Information Matters: Learning Relation and Topology for Occluded Person Re-Identification
Occluded person re-identification (ReID) aims to match occluded person images to holistic ones across dis-joint cameras. In this paper, we propose a novel framework by learning high-order relation and topology informatio…
Graph MatchingOccluded Person Re-IdentificationPerson Re-IdentificationRelationOn the current failure -- but bright future -- of topology-driven biological network alignment
The function of a protein is defined by its interaction partners. Thus, topology-driven network alignment of the protein-protein interaction (PPI) networks of two species should uncover similar interaction patterns and a…
Multi-resolution Shape Analysis via Non-Euclidean Wavelets: Applications to Mesh Segmentation and Surface Alignment Problems
The analysis of 3-D shape meshes is a fundamental problem in computer vision, graphics, and medical imaging. Frequently, the needs of the application require that our analysis take a multi-resolution view of the shape's …
High Speed All-optical extended DV-Curve-based DNA sequence alignment utilizing wavelength and polarization modulation
This paper presents a novel optical processing approach for exploring genome sequences built upon optical correlator for global alignment and extended DV-curve method for local alignment. To overcome the problem of tradi…
All