Clustering the biological networks using shortest path

The aim of graph clustering is to partition the given graph into subgraphs, and then assign the subgraphs to overlapping or non-overlapping clusters. In this process, densely connected subgraphs fall into a single cluster, thereby maximizing the intra-cluster similarity. Here we propose a clustering...

Full description

Saved in:
Bibliographic Details
Published in:Procedia computer science 2020, Vol.171, p.755-760
Main Authors: Warrier, Nandini J, Chacko, Daphna, Krishnan, K Murali
Format: Article
Language:English
Subjects:
05C40
05C90
92B05
Chordal
Clustering
Cographs
Graphs
Orthology Relations
Outerplanar
Phylogeny 2000 MSC: 05C12
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The aim of graph clustering is to partition the given graph into subgraphs, and then assign the subgraphs to overlapping or non-overlapping clusters. In this process, densely connected subgraphs fall into a single cluster, thereby maximizing the intra-cluster similarity. Here we propose a clustering method based on the shortest path between the nodes. We propose a 2- partition in a few graph classes namely outerplanar graphs, graphs with simplicial vertices, chordal graphs, distance hereditary graphs and cographs. The solution to the chordal and outerplanar graphs can be found in linear time. Chordal graphs are widely used in perfect phylogeny related research whereas cographs are used to model the orthology relations. Hence a clustering method based on shortest path in chordal graphs and cographs may have significant impact in the research related to orthologous genes as well as phylogenetic relations.
ISSN:1877-0509
1877-0509
DOI:10.1016/j.procs.2020.04.082