Lesson plan
Graph Aligner
Graph Aligner (GRAAL) is an algorithm for global network alignment that is based solely on network topology. It aligns two networks G and H by producing an alignment that consists of a set of ordered pairs (x, y) , where x is a node in G and y is a node in H . GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities, where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods (out to distance 4). GRAAL produces global alignments (i.e., it aligns each node in the smaller network to exactly one node in the larger network). The matching proceeds using a technique analogous to the "seed and extend" approach of the popular BLAST algorithm for sequence alignment: it first chooses a single "seed" pair of nodes (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm (see [Kuchaiev et al., 2010] for details).
Article summary
Graph Aligner (GRAAL) is an algorithm for global network alignment that is based solely on network topology. It aligns two networks G and H by producing an alignment that consists of a set of ordered pairs (x, y) , where x is a node in G and y is a node in H . GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities, where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods (out to distance 4). GRAAL produces global alignments (i.e., it aligns each node in the smaller network to exactly one node in the larger network). The matching proceeds using a technique analogous to the "seed and extend" approach of the popular BLAST algorithm for sequence alignment: it first chooses a single "seed" pair of nodes (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm (see [Kuchaiev et al., 2010] for details).
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.