Least resolved trees for two-colored best match graphs
2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive graphs that appears in phylogenetic combinatorics. There, 2-BMGs describe evolutionarily most closely related genes between a pair of species. They are explained by a unique least resolved tree (LRT). Introducing the concept of support vertices we derive an $O(|V|+|E|\log^2|V|)$-time algorithm to recognize 2-BMGs and to construct its LRT. The approach can be extended to also recognize binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
On the Hardness of Optimal Motion on Trees
This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives--distance, makespan, and flowtime--for both labeled and colored variants. In MAPF,…
Whole Genome Phylogenetic Tree Reconstruction Using Colored de Bruijn Graphs
We present kleuren, a novel assembly-free method to reconstruct phylogenetic trees using the Colored de Bruijn Graph. kleuren works by constructing the Colored de Bruijn Graph and then traversing it, finding bubble struc…
Mean Square Performance of a family of Adaptive Algorithms for colored noise
In real-time applications the characteristics and properties of a signal vary inconsistently. So, to maintain the integrity of such signals there is a need for effective adaptive filters. The conventional Least Mean Squa…
PhylaFlow: Hybrid Flow Matching in Billera-Holmes-Vogtmann Tree Space for Phylogenetic Inference
Phylogenetic trees are hybrid objects: branch lengths vary continuously, while topologies change discretely through edge contractions and expansions. Billera-Holmes-Vogtmann (BHV) tree space provides a canonical geometry…
Parsing into Variable-in-situ Logico-Semantic Graphs
We propose variable-in-situ logico-semantic graphs to bridge the gap between semantic graph and logical form parsing. The new type of graph-based meaning representation allows us to include analysis for scope-related phe…
Negationvalid