Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

DOI10.1137/22m150736xarXiv2112.00403OpenAlexW4387060342MaRDI QIDQ6072286

Marc Hellmuth, David Schaller, Peter F. Stadler

Publication date: 13 October 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partitionlinear-time algorithmhorizontal gene transferxenologyFitch graphgene families

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) General biology and biomathematics (92B05)

Cites Work

• Unnamed Item
• The level ancestor problem simplified
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Finding level-ancestors in trees
• Reconstructing gene trees from Fitch's xenology relation
• Orthology relations, symbolic ultrametrics, and cographs
• Indirect identification of horizontal gene transfer
• Best match graphs with binary trees
• Compatibility of partitions with trees, hierarchies, and split systems
• Alternative characterizations of Fitch's xenology relation
• Best match graphs
• Complete characterization of incorrect orthology assignments in best match graphs
• Complexity of modification problems for best match graphs
• Least resolved trees for two-colored best match graphs
• Forbidden time travel: Characterization of time-consistent tree reconciliation maps
• A short note on undirected Fitch graphs
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees