2015/10/30 by Momoko Hayamizu, Hayamizu, Momoko, Hiroshi Endô +3
Biochemistry, Genetics and Molecular Biology · #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Gene Regulatory Network Analysis #Gene expression and cancer classification #Populations and Evolution (q-bio.PE) #Primary 05C12 #Quantitative Methods (q-bio.QM) #Secondary 05C05 #Single-cell and spatial transcriptomics
paper · pdf · doi:10.48550/arxiv.1510.09155
openalex publication_date 2015/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recent years have witnessed a surge of biological interest in the minimum spanning tree (MST) problem for its relevance to automatic model construction using the distances between data points. Despite the increasing use of MST algorithms for this purpose, the goodness-of-fit of an MST to the data is often elusive because no quantitative criteria have been developed to measure it. Motivated by this, we provide a necessary and sufficient condition to ensure that a metric space on n points can be represented by a fully labeled tree on n vertices, and thereby determine when an MST preserves all pairwise distances between points in a finite metric space.