Recognizing and realizing cactus metrics

Hayamizu, Momoko, Huber, Katharina, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Murakami, Yukihiro (2020) Recognizing and realizing cactus metrics. Information Processing Letters, 157. ISSN 0020-0190

Preview	PDF (Published_Version) - Published Version Available under License Creative Commons Attribution. Download (281kB) | Preview
Preview	PDF (Proof_Version) Available under License Creative Commons Attribution. Download (387kB) | Preview

Abstract

The problem of realizing finite metric spaces in terms of weighted graphs has many applications. For example, the mathematical and computational properties of metrics that can be realized by trees have been well-studied and such research has laid the foundation of the reconstruction of phylogenetic trees from evolutionary distances. However, as trees may be too restrictive to accurately represent real-world data or phenomena, it is important to understand the relationship between more general graphs and distances. In this paper, we introduce a new type of metric called a cactus metric, that is, a metric that can be realized by a cactus graph. We show that, just as with tree metrics, a cactus metric has a unique optimal realization. In addition, we describe an algorithm that can recognize whether or not a metric is a cactus metric and, if so, compute its optimal realization in $O(n^3)$ time, where $n$ is the number of points in the space.

Item Type:	Article
Uncontrolled Keywords:	algorithm,algorithms,cactus metric,distance matrices,metric realization,optimal realization,phylogenetic network,spaces,trees
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	18 Mar 2020 06:37
Last Modified:	21 Apr 2023 00:20
URI:	https://ueaeprints.uea.ac.uk/id/eprint/73659
DOI:	10.1016/j.ipl.2020.105916

Downloads

Actions (login required)

View Item