Open AccessCySpanningTree: Minimal Spanning Tree computation in Cytoscape
Author(s) -
Faizaan Shaik,
Srikanth Bezawada,
Neena Goveas
Publication year - 2015
Publication title -
f1000research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.099
H-Index - 60
ISSN - 2046-1402
DOI - 10.12688/f1000research.6797.1
Subject(s) - minimum spanning tree , spanning tree , computer science , steiner tree problem , heuristic , minimum degree spanning tree , tree (set theory) , kruskal's algorithm , travelling salesman problem , graph , computation , theoretical computer science , algorithm , mathematics , artificial intelligence , combinatorics
Simulating graph models for real world networks is made easy using software tools like Cytoscape. In this paper, we present the open-source CySpanningTree app for Cytoscape that creates a minimal/maximal spanning tree network for a given Cytoscape network. CySpanningTree provides two historical ways for calculating a spanning tree: Prim’s and Kruskal’s algorithms. Minimal spanning tree discovery in a given graph is a fundamental problem with diverse applications like spanning tree network optimization protocol, cost effective design of various kinds of networks, approximation algorithm for some NP-hard problems, cluster analysis, reducing data storage in sequencing amino acids in a protein, etc. This article demonstrates the procedure for extraction of a spanning tree from complex data sets like gene expression data and world network. The article also provides an approximate solution to the traveling salesman problem with minimum spanning tree heuristic. CySpanningTree for Cytoscape 3 is available from the Cytoscape app store.