LGM: Mining Frequent Subgraphs from Linear Graphs

A linear graph is a graph whose vertices are totally ordered. Biological and linguistic sequences with interactions among symbols are naturally represented as linear graphs. Examples include protein contact maps, RNA secondary structures and predicate-argument structures. Our algorithm, linear graph...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-03
Main Authors: Tabei, Yasuo, Okanohara, Daisuke, Hirose, Shuichi, Tsuda, Koji
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Enumeration
Graph theory
Graphical representations
Graphs
Proteins
Ribonucleic acid
RNA
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A linear graph is a graph whose vertices are totally ordered. Biological and linguistic sequences with interactions among symbols are naturally represented as linear graphs. Examples include protein contact maps, RNA secondary structures and predicate-argument structures. Our algorithm, linear graph miner (LGM), leverages the vertex order for efficient enumeration of frequent subgraphs. Based on the reverse search principle, the pattern space is systematically traversed without expensive duplication checking. Disconnected subgraph patterns are particularly important in linear graphs due to their sequential nature. Unlike conventional graph mining algorithms detecting connected patterns only, LGM can detect disconnected patterns as well. The utility and efficiency of LGM are demonstrated in experiments on protein contact maps.
ISSN:2331-8422