# Beyond representing orthology relations by trees

Huber, Katharina and Scholz, Guillaume (2018) Beyond representing orthology relations by trees. Algorithmica, 80 (1). 73–103. ISSN 0178-4617

PDF (Accepted manuscript) - Submitted Version
Restricted to Repository staff only until 31 December 2099.

Download (876kB) | Request a copy
 Preview
PDF (10.1007_s00453-016-0241-9) - Published Version
Available under License Creative Commons Attribution.

Download (786kB) | Preview

## Abstract

Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple relations on a set of sequences called orthology relations may be employed. In addition to being interesting from a practical point of view they are also attractive from a theoretical perspective in that e.\,g.\,a characterization is known for when such a relation is representable by a certain type of phylogenetic tree. For an orthology relation inferred from real biological data it is however generally too much to hope for that it satisfies that characterization. Rather than trying to correct the data in some way or another which has its own drawbacks, as an alternative, we propose to represent an orthology relation $\delta$ in terms of a structure more general than a phylogenetic tree called a phylogenetic network. To compute such a network in the form of a level-1 representation for $\delta$, we formalize an orthology relation in terms of the novel concept of a symbolic 3- dissimilarity which is motivated by the biological concept of a cluster of orthologous groups'', or COG for short. For such maps which assign symbols rather that real values to elements, we introduce the novel {\sc Network-Popping} algorithm which has several attractive properties. In addition, we characterize an orthology relation $\delta$ on some set $X$ that has a level-1 representation in terms of eight natural properties for $\delta$ as well as in terms of level-1 representations of orthology relations on certain subsets of $X$.

Item Type: Article © The Author(s) 2016 Open Access: This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. orthology relation,phylogenetic network,level-1 network,trinet,3-dissimilarity,cog Faculty of Science > School of Computing SciencesFaculty of Science Pure Connector 28 Oct 2016 16:00 19 Sep 2019 00:10 https://ueaeprints.uea.ac.uk/id/eprint/61155 10.1007/s00453-016-0241-9

### Actions (login required)

 View Item