Beyond representing orthology relations by trees

DOI10.1007/S00453-016-0241-9zbMATH Open1392.92055arXiv1603.04632OpenAlexW2301157271MaRDI QIDQ1702121FDOQ1702121

Authors: G. E. Scholz, Katharina T. Huber 

Publication date: 28 February 2018

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple operations 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 introduce the novel {sc Network-Popping} algorithm which has several attractive properties. In addition, we characterize orthology relations $delta$ on some set $X$ that have a level-1 representation in terms of eight natural properties for $delta$ as well as in terms for level-1 representations of orthology relations on certain subsets of $X$.

Full work available at URL: https://arxiv.org/abs/1603.04632

Recommendations

• Tree representations via ordinal machines
• Trees and semantics
• Recognizing relations by tree automata
• CHARACTERIZING TREES IN CONCEPT LATTICES
• Semantics of trees
• scientific article; zbMATH DE number 1303445
• Structural characterizations of the navigational expressiveness of relation algebras on a tree
• Trees in Concept Lattices
• Semantic trees revisited: some new completeness results
• scientific article; zbMATH DE number 475422

zbMATH Keywords

phylogenetic networklevel-1 networktrinet3-dissimilaritycogorthology relation

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15) Trees (05C05)

Cites Work

• Title not available (Why is that?)
• Trinets encode tree-child and level-2 phylogenetic networks
• On encodings of phylogenetic networks of bounded level
• Encoding and constructing 1-nested phylogenetic networks with trinets
• Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Orthology relations, symbolic ultrametrics, and cographs
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
• Orthology relation and gene tree correction: complexity results

Cited In (10)

• Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Shared ancestry graphs and symbolic arboreal maps
• Orthology relations, symbolic ultrametrics, and cographs
• Partial homology relations -- satisfiability in terms of di-cographs
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Three-way symbolic tree-maps and ultrametrics
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Recovering normal networks from shortest inter-taxa distance information
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results

Uses Software

• Notung
• ecceTERA

This page was built for publication: Beyond representing orthology relations by trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702121)