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

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
Additional Information:	© 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.
Uncontrolled Keywords:	orthology relation,phylogenetic network,level-1 network,trinet,3-dissimilarity,cog
Faculty \ School:	Faculty of Science > School of Computing Sciences Faculty of Science
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology
Depositing User:	Pure Connector
Date Deposited:	28 Oct 2016 16:00
Last Modified:	14 Jun 2023 12:45
URI:	https://ueaeprints.uea.ac.uk/id/eprint/61155
DOI:	10.1007/s00453-016-0241-9

Downloads

Actions (login required)

View Item