Publication Type

Journal Article

Version

publishedVersion

Publication Date

1-2014

Abstract

Coupling graphs are newly introduced in this paper to meet many application needs particularly in the field of bioinformatics. A coupling graph is a two-layer graph complex, in which each node from one layer of the graph complex has at least one connection with the nodes in the other layer, and vice versa. The coupling graph model is sufficiently powerful to capture strong and inherent associations between subgraph pairs in complicated applications. The focus of this paper is on mining algorithms of frequent coupling subgraphs and bioinformatics application. Although existing frequent subgraph mining algorithms are competent to identify frequent subgraphs from a graph database, they perform poorly on frequent coupling subgraph mining because they generate many irrelevant subgraphs. We propose a novel graph transformation technique to transform a coupling graph into a generic graph. Based on the transformed coupling graphs, existing graph mining methods are then utilized to discover frequent coupling subgraphs. We prove that the transformation is precise and complete and that the restoration is reversible. Experiments carried out on a database containing 10,511 coupling graphs show that our proposed algorithm reduces the mining time very much in comparison with the existing subgraph mining algorithms. Moreover, we demonstrate the usefulness of frequent coupling subgraphs by applying our algorithm to make accurate predictions of epitopes in antibody-antigen binding.

Keywords

Coupling graph, epitope prediction, graph mining, graph transformation

Discipline

Biomedical Engineering and Bioengineering | Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

IEEE/ACM Transactions on Computational Biology and Bioinformatics

Volume

11

Issue

1

First Page

7

Last Page

16

ISSN

1545-5963

Identifier

10.1109/TCBB.2013.136

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Additional URL

https://doi.org/10.1109/TCBB.2013.136

Download

Share

COinS