Dataset Information

Degree sums and dense spanning trees.

ABSTRACT: Finding dense spanning trees (DST) in unweighted graphs is a variation of the well studied minimum spanning tree problem (MST). We utilize established mathematical properties of extremal structures with the minimum sum of distances between vertices to formulate some general conditions on the sum of vertex degrees. We analyze the performance of various combinations of these degree sum conditions in finding dense spanning subtrees and apply our approach to practical examples. After briefly describing our algorithm we also show how it can be used on variations of DST, motivated by variations of MST. Our work provide some insights on the role of various degree sums in forming dense spanning trees and hopefully lay the foundation for finding fast algorithms or heuristics for related problems.

SUBMITTER: Li T

PROVIDER: S-EPMC5605090 | biostudies-literature | 2017

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Degree sums and dense spanning trees.

Li Tao T Gao Yingqi Y Dong Qiankun Q Wang Hua H

PloS one 20170919 9

Finding dense spanning trees (DST) in unweighted graphs is a variation of the well studied minimum spanning tree problem (MST). We utilize established mathematical properties of extremal structures with the minimum sum of distances between vertices to formulate some general conditions on the sum of vertex degrees. We analyze the performance of various combinations of these degree sum conditions in finding dense spanning subtrees and apply our approach to practical examples. After briefly describ ...[more]

PMID: 28926585

Similar Datasets

Project description:BackgroundVisualization tools allow researchers to obtain a global view of the interrelationships between the probes or experiments of a gene expression (e.g. microarray) data set. Some existing methods include hierarchical clustering and k-means. In recent years, others have proposed applying minimum spanning trees (MST) for microarray clustering. Although MST-based clustering is formally equivalent to the dendrograms produced by hierarchical clustering under certain conditions; visually they can be quite different.MethodsHAMSTER (Helpful Abstraction using Minimum Spanning Trees for Expression Relations) is an open source system for generating a set of MSTs from the experiments of a microarray data set. While previous works have generated a single MST from a data set for data clustering, we recursively merge experiments and repeat this process to obtain a set of MSTs for data visualization. Depending on the parameters chosen, each tree is analogous to a snapshot of one step of the hierarchical clustering process. We scored and ranked these trees using one of three proposed schemes. HAMSTER is implemented in C++ and makes use of Graphviz for laying out each MST.ResultsWe report on the running time of HAMSTER and demonstrate using data sets from the NCBI Gene Expression Omnibus (GEO) that the images created by HAMSTER offer insights that differ from the dendrograms of hierarchical clustering. In addition to the C++ program which is available as open source, we also provided a web-based version (HAMSTER+) which allows users to apply our system through a web browser without any computer programming knowledge.ConclusionResearchers may find it helpful to include HAMSTER in their microarray analysis workflow as it can offer insights that differ from hierarchical clustering. We believe that HAMSTER would be useful for certain types of gradient data sets (e.g time-series data) and data that indicate relationships between cells/tissues. Both the source and the web server variant of HAMSTER are available from http://hamster.cbrc.jp/.

Dataset Information

Degree sums and dense spanning trees.

Publications

Degree sums and dense spanning trees.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets