Clustering the biological networks using shortest path
| Autor: | Nandini J Warrier, Daphna Chacko, K. Murali Krishnan |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Combinatorics
Phylogenetic tree Computer science Perfect phylogeny Partition (database) Graph Vertex (geometry) Combinatorics Computer Science::Discrete Mathematics Chordal graph Shortest path problem General Earth and Planetary Sciences Partition (number theory) Computer Science::Data Structures and Algorithms Cluster analysis Time complexity Biological network MathematicsofComputing_DISCRETEMATHEMATICS General Environmental Science Clustering coefficient |
| Zdroj: | Procedia Computer Science. 171:755-760 |
| ISSN: | 1877-0509 |
| DOI: | 10.1016/j.procs.2020.04.082 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|