Huber, Katharina T., Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 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: | |

Depositing User: | LivePure Connector |

Date Deposited: | 28 Jun 2024 12:31 |

Last Modified: | 21 Oct 2024 09:30 |

URI: | https://ueaeprints.uea.ac.uk/id/eprint/95704 |

DOI: | 10.1137/23M1573318 |

## Downloads

Downloads per month over past year

### Actions (login required)

View Item |