Comparative Genomics: 20th International Conference, RECOMB-CG 2023, Istanbul, Turkey, April 14–15, 2023, Proceedings

Preface
Organization
Contents
Classifying the Post-duplication Fate of Paralogous Genes
	1 Introduction
	2 Post-duplication Fates
	3 Methods
		3.1 Classifying the Fates of Paralogs
		3.2 Computing the Fate Between All Paralogs in a Gene Tree
		3.3 Simulations
	4 Results
	5 Discussion
	References
Inferring Clusters of Orthologous and Paralogous Transcripts
	1 Introduction
	2 Preliminaries: Phylogenetic Trees, Reconciliation, Orthology, Paralogy
	3 A Graph-Based Algorithm to Infer Isoorthology and Recent Paralogy Relations Between Transcripts
		3.1 Pairwise Similarity Score Between Transcripts
		3.2 Orthology Graph Construction and Ortholog Groups Inference
	4 Results and Discussion
		4.1 Comparison with Ortholog Groups Predicted in Human, Mouse and Dog One-to-one Orthologous Genes
		4.2 Comparison of the Proportions of Ortho-orthologs, Para-orthologs and Recent Paralogs Predicted
	5 Conclusion
	References
On the Class of Double Distance Problems
	1 Introduction
	2 Background
		2.1 Comparing Canonical Genomes
		2.2 Comparing a Singular and a Duplicated Genome
	3 Equivalence of kDoubleDistance and kDisambiguation
		3.1 Ambiguous Breakpoint Graph
		3.2 The Class of sigmaK Disambiguations
	4 First Steps to Solve the sigmak Disambiguation
		4.1 Common Adjacencies and Telomeres Are Conserved
		4.2 Symmetric Squares Can Be Fixed Arbitrarily
		4.3 A Linear Time Greedy Algorithm for the sigma4 Disambiguation
		4.4 Pruning ABGSD for the sigma6 Disambiguation
	5 Solving the General sigma6 Disambiguation in Linear Time
		5.1 Intersection Between Players
		5.2 Intersection Graph of an Ambiguous Component
		5.3 Path-Flows in the Intersection Graph
		5.4 Cycle-Bubbles in the Intersection Graph
		5.5 What Remains Is a Set of Independent Unsaturated Path-Lines
	6 Final Remarks and Discussion
	References
The Floor Is Lava - Halving Genomes with Viaducts, Piers and Pontoons
	1 Introduction
	2 Problem Definition
	3 The Properties of Simple Rearrangement Graphs
	4 DCJ-Indel Halving for Genomes with Resolved Homology
	5 Conclusion and Outlook
	References
Two Strikes Against the Phage Recombination Problem
	1 Introduction
	2 Basic Definitions and Properties
	3 Reconstructing One Target Genome
		3.1 The () Direction
		3.2 The () Direction
	4 NP-hardness for Genomes of Length 4
		4.1 The () Direction
		4.2 The () Direction
	5 Conclusion
	References
Physical Mapping of Two Nested Fixed Inversions in the X Chromosome of the Malaria Mosquito Anopheles messeae
	1 Introduction
	2 Material and Methods
		2.1 Collection of Mosquitoes and Species Identification
		2.2 Chromosome Preparation and Karyotyping
		2.3 Marker Genes Selection, DNA Probes Development and Synthesis
		2.4 DNA Labeling and Fluorescence in Situ Hybridization (FISH)
		2.5 Microscopy and Physical Mapping
		2.6 Computational Pair-Wise Analysis of Rearrangements
		2.7 Transposable Element (TE) and Simple Repeat Annotation
		2.8 Statistical Analyses
	3 Results
		3.1 Physical Mapping of Inversion Breakpoint Regions
		3.2 Reconstruction of the X Chromosome Rearrangements Using Synteny Blocks
		3.3 The Genomic Content in the Neighborhoods of the Breakpoint Regions
	4 Discussion
	References
Gene Order Phylogeny via Ancestral Genome Reconstruction Under Dollo
	1 Introduction
	2 Dollo's Law in the Context of Unrooted Binary Trees
	3 Generic Algorithm
	4 Genomics Case: Generalized Adjacencies of Genes
		4.1 Algorithm: Ancestor via Maximum Weight Matching (MWM)
	5 Application to Phylogenies of Three Plant Orders
		5.1 Asterales
		5.2 Fagales
		5.3 Sapindales
	6 Discussion and Conclusions
	References
Prior Density Learning in Variational Bayesian Phylogenetic Parameters Inference
	1 Introduction
	2 Background
		2.1 Notation
		2.2 Bayesian Phylogenetic Parameter Inference
		2.3 Variational Inference and Parameterization
	3 New Approach
		3.1 Gradient-Based Learning Prior Density
		3.2 Neural Network-Based Prior Parameterization
	4 Experimental Study
		4.1 Dataset Simulation Procedure
		4.2 Variational Inference Settings
		4.3 Performance Metrics
	5 Results
		5.1 Branch Lengths Estimation Performance
		5.2 Substitution Model Parameters Estimation Performance
		5.3 Convergence Analysis
	6 Discussion
	References
The Asymmetric Cluster Affinity Cost
	1 Introduction
	2 Asymmetric Cluster Affinity Cost
		2.1 Tree Edit Operations
		2.2 Algorithm for the Cluster Affinity Cost
		2.3 Cluster Affinity for Multi-copy Gene Trees
		2.4 NNI Search Using Cluster Affinity Heuristic
		2.5 Diameter of the Cluster Affinity Cost
		2.6 Separation Diameter
	3 Empirical Study
		3.1 CA Displays a Broad Distribution Range
		3.2 CA Is Robust to Minor Tree Edit Operations
	4 Conclusion
	References
The K-Robinson Foulds Measures for Labeled Trees
	1 Introduction
	2 Concepts and Notations
		2.1 Trees
		2.2 Rooted Trees
		2.3 Labeled Trees
		2.4 Phylogenetic and Mutation Trees
		2.5 Dissimilarity Measures for Trees
	3 The k-RF Dissimilarity Measures for 1-Labeled Trees
		3.1 The k-RF Measures for 1-Labeled Trees
		3.2 The k-RF Measures for 1-Labeled Rooted Trees
	4 Characterization of k-RF for 1-Labeled Trees
		4.1 Mathematical Properties
		4.2 The Distribution of k-RF Scores
	5 A Generalization to Multiset-Labeled Trees
		5.1 Multisets and Their Operations
		5.2 The RF and k-RF Measures for Multiset-Labeled Trees
		5.3 The k-RF Measures for Multiset-Labeled Rooted Trees
		5.4 Correlation Between the k-RF and the Other Measures
	6 Validating the k-RF Measures by Clustering Trees
	7 Conclusions
	References
Bounding the Number of Reticulations in a Tree-Child Network that Displays a Set of Trees
	1 Introduction
	2 Lower Bounds on the Tree-Child Reticulation Number by Integer Programming
		2.1 TCLB1: A Simple Lower Bound
		2.2 TCLB2: A Stronger Lower Bound
	3 Cherry Bound: Analytical Lower Bound in Terms of the Number of Distinct Cherries in the Given Trees
	4 Results
		4.1 Simulation Data
		4.2 Real Biological Data
	5 Conclusion
	References
Finding Agreement Cherry-Reduced Subnetworks in Level-1 Networks
	1 Introduction
	2 Preliminaries
		2.1 Networks
		2.2 Cherries and Cherry Reductions
		2.3 Maximum Agreement Cherry-Reduced Subnetworks
	3 An MACRS Algorithm on Level-1 Networks
	4 Subroutines
		4.1 Enumerating the Set of Reticulation-Trimmed Subnetworks
		4.2 An Algorithm for MACRS-Simple
		4.3 Complexity of Algorithm1
	5 Conclusion and Discussion
	References
CONSULT-II: Taxonomic Identification Using Locality Sensitive Hashing
	1 Introduction
	2 Algorithm
		2.1 Background: Review of CONSULT
		2.2 Overview of Changes
		2.3 Automatic Setting of Hash Table Parameters
		2.4 Library Construction: Saving Taxonomic IDs per k-mer
		2.5 Query and Taxonomic Identification
	3 Experimental Setup
		3.1 Experiments
	4 Results
		4.1 Controlled Novelty Experiment
		4.2 CAMI Profiling Results
	5 Discussion
	References
MAGE: Strain Level Profiling of Metagenome Samples
	1 Introduction
	2 Methods
		2.1 Abundance Estimation and MLE
		2.2 Constrained Optimization and Strain Level Coverage
		2.3 Local Search and Strain Set Refinement
		2.4 Read Mapping
	3 Results
	4 Conclusion
	References
MoTERNN: Classifying the Mode of Cancer Evolution Using Recursive Neural Networks
	1 Introduction
	2 Methods
		2.1 Problem Description
		2.2 Recursive Neural Networks
		2.3 Encoder Network
		2.4 Compositionality Function
		2.5 Classifier Network
		2.6 Loss Function
		2.7 Simulation Design
	3 Results and Discussion
		3.1 Supervised Training of MoTERNN
		3.2 Application to Real Data
	4 Summary and Future Directions
	5 Competing Interests
	References
Author Index