Shared ancestry graphs and symbolic arboreal maps

Huber, Katharina T., Moulton, Vincent and Scholz, Guillaume E. (2024) Shared ancestry graphs and symbolic arboreal maps. SIAM Journal on Discrete Mathematics, 38 (4). pp. 2553-2577. ISSN 0895-4801

Preview

PDF (arboreal-revised-siam) - Accepted Version Available under License Creative Commons Attribution. Download (461kB) | Preview

Abstract

A network N on a finite set X, | X| geq 2, is a connected directed acyclic graph with leaf set X in which every root in N has outdegree at least 2 and no vertex in N has indegree and outdegree equal to 1; N is arboreal if the underlying unrooted, undirected graph of N is a tree. Networks are of interest in evolutionary biology since they are used, for example, to represent the evolutionary history of a set X of species whose ancestors have exchanged genes in the past. For M some arbitrary set of symbols, d : ( X 2 ) → M ∪ {⊙ } is a symbolic arboreal map if there exists some arboreal network N whose vertices with outdegree 2 or more are labeled by elements in M and so that d({ x, y} ), { x, y} ∈ ( X 2 ) , is equal to the label of the least common ancestor of x and y in N if this exists, and ⊙ otherwise. Important examples of symbolic arboreal maps include the symbolic ultrametrics, which arise in areas such as game theory, phylogenetics, and cograph theory. In this paper we show that a map d : ( X 2 ) → M ∪ { ⊙} is a symbolic arboreal map if and only if d satisfies certain 3- and 4-point conditions and the graph with vertex set X and edge set consisting of those pairs { x, y} ∈ ( X 2 ) with d({ x, y} ) not =odot is Ptolemaic (i.e., its shortest path distance satisfies Ptolemy's inequality). To do this, we introduce and prove a key theorem concerning the shared ancestry graph for a network N on X, where this is the graph with vertex set X and edge set consisting of those { x, y} ∈ ( X 2 ) such that x and y share a common ancestor in N. In particular, we show that for any connected graph G with vertex set X and edge clique cover K in which there are no two distinct sets in K with one a subset of the other, there is some network with | K| roots and leaf set X whose shared ancestry graph is G.

Item Type:	Article
Uncontrolled Keywords:	ptolemaic graphs,arboreal networks,cographs,symbolic maps,ultrametrics,mathematics(all) ,/dk/atira/pure/subjectarea/asjc/2600
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:	28 Jun 2024 12:31
Last Modified:	06 Feb 2025 12:04
URI:	https://ueaeprints.uea.ac.uk/id/eprint/95704
DOI:	10.1137/23M1573318

Downloads

Actions (login required)

View Item