Comparative Genomics: 19th International Conference, RECOMB-CG 2022, La Jolla, CA, USA, May 20–21, 2022, Proceedings (Lecture Notes in Computer Science, 13234)

Preface
Organization
Contents
Evolution
On the Comparison of Bacteriophage Populations
	1 Introduction
		1.1 Recombinations and Mosaicism in Phage Genomes
		1.2 Recombination Between Phage Populations
	2 Methods
		2.1 Basic Definitions and Properties
		2.2 Minimum Covers
		2.3 Lower Bounds
	3 Experiments
		3.1 Dataset Construction
		3.2 Comparing Factories
		3.3 Shared Evolution
		3.4 Population Structure
	4 Discussion and Conclusion
	References
Syntenic Dimensions of Genomic Evolution
	1 Introduction
	2 The Construction and Biological Significance of Synteny Blocks
	3 Review of Sequence Divergence
	4 Fractionation and Gap Size
	5 Spatial Evolution
	6 Data Summary
	7 Correlational Analysis
	8 Discussion
	References
Phylogenetics
Fast and Accurate Branch Support Calculation for Distance-Based Phylogenetic Placements
	1 Introduction
	2 Approach
		2.1 Background on APPLES-2
		2.2 Distance-Based Support Estimation: Goals and Background
		2.3 Non-parametric Bootstrapping
		2.4 Parametric Bootstrapping (Binomial and Poisson Models)
	3 Experimental Study
		3.1 Dataset
		3.2 Measurements
	4 Results and Discussion
		4.1 Simulated Single-Gene RNASim Dataset: Full-Length Sequences
		4.2 Simulated Single-Gene RNASim Dataset: Fragmentary Sequences
		4.3 Multi-gene Web of Life (WoL) Dataset
		4.4 Runtimes
	5 Discussions
	References
The Sackin Index of Simplex Networks
	1 Introduction
	2 Basic Concepts and Notation
		2.1 Tree-Child Networks
		2.2 Node Depth, Network Height and Sackin Index
	3 The Expected Sackin Index of Random Simplex Networks
		3.1 Enumerating Simplex Networks
		3.2 The Total Depths of the Nodes in the Top Tree Component
		3.3 The Expected Total C-Depth of Random Simplex Networks
		3.4 Bounds on the Sackin Index for a Random Simplex Network
	4 Conclusion
	References
Phylogenetic Placement Problem: A Hyperbolic Embedding Approach
	1 Introduction
	2 Background on Hyperbolic Spaces
	3 Problem Definition
	4 H-DEPP
	5 Experimental Setup
		5.1 Datasets
		5.2 Evaluation
	6 Results and Discussions
		6.1 Comparison of H-DEPP Alternatives
		6.2 Comparison to Euclidean Embedding
		6.3 Tree Updates
	7 Conclusions and Future Work
	References
Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into Account
	1 Introduction
	2 Methods
		2.1 Rooted Network Branch Score (rNBS)
		2.2 Average Path Distance (APD)
	3 Results and Discussion
		3.1 Dissimilarity Under Various Network Perturbations
		3.2 Analyzing Posterior Samples Using the Dissimilarity Measures
		3.3 Runtime Comparison
	4 Conclusions and Future Work
	References
Homology and Reconciliation
The Complexity of Finding Common Partitions of Genomes with Predefined Block Sizes
	1 Introduction
	2 Preliminary Notions
	3 The Exact F-Strip Recovery Problem with Fixed F
	4 GSR-F in Polynomial Time for Fixed F and Alphabet
	5 Fixed Alphabet with Unbounded F is NP-Hard
	6 Conclusion
	References
Reconciliation with Segmental Duplication, Transfer, Loss and Gain
	1 Introduction
	2 Preliminary Definitions
	3 Evolutionary Histories for Syntenies
	4 Most Parsimonious Super-Reconciliations
	5 A Two-Steps Method
	6 A Dynamic Programming Algorithm for DTL Super-Reconciliation
	7 Application to CRISPR-Associated (Cas) Gene Syntenies
		7.1 Cas Gene Syntenies
		7.2 Dataset
	8 Results
		8.1 DTL Super-Reconciliation Settings
		8.2 An Evolutionary Scenario
	9 Conclusion
	A  Additional Content for Sect. 4 (``Most Parsimonious  Super-Reconciliations'')
	B  Additional Content for Sect. 6 (``A Dynamic  Programming Algorithm for DTL Super- Reconciliation'')
	References
Quantifying Hierarchical Conflicts in Homology Statements
	1 Introduction
	2 Methodological Foundations
		2.1 Overlapping Homology Statements and the Block Graph
		2.2 Homology Witnesses and Block Hierarchies
		2.3 Relating Block Hierarchy to Stars in the Block Graph
	3 Algorithms
		3.1 NP-Hardness of MDDS
		3.2 A Heuristic for MDDS
	4 Quantifying Hierarchical Conficts
		4.1 Discordance Ratio and Distinction from Jaccard Index
		4.2 Mycobacterium Tuberculosis Clinical Isolates
		4.3 Alignathon
	5 Discussion and Conclusions
	A NP-Hardness of MDDS
	B Collections of Block that are not Clean
	C Segmental Duplications
	References
On Partial Gene Transfer and Its Impact on Gene Tree Reconstruction
	1 Introduction
	2 Materials and Methods
		2.1 Simulated Datasets
		2.2 Biological Datasets
		2.3 Gene Tree Construction and Comparison
		2.4 Using PhyML-Multi to Detect PGTs
	3 Trippd: Tri-Partition Based PGT Detection
	4 Results
		4.1 Impact of PGT on Gene Tree Reconstruction Accuracy
		4.2 PGT Detection Accuracy
		4.3 Application to Biological Datasets
	5 Discussion and Conclusion
	References
Genome Rearrangements
Sorting by k-Cuts on Signed Permutations
	1 Introduction
	2 Basic Definitions
	3 Breakpoints and Strips
		3.1 SKCBR  is NP-Hard for k 5
	4 An Approximation Algorithm for SKCBR
	5 Cycle Graph and Complement Cycle Graph
	6 Increasing the Number of Cycles in G() with 4-Cuts
	7 A 1.5-Approximation Algorithm for SKCBR When k=4
	8 Conclusion
	References
A New Approach for the Reversal Distance with Indels and Moves in Intergenic Regions
	1 Introduction
	2 Background
		2.1 Weighted Breakpoint Graph
	3 Results
		3.1 Complexity Analysis
		3.2 Lower Bounds
		3.3 Reversal and Move Operations
		3.4 Reversal, Move, and Indel Operations
	4 Conclusion
	References
.26em plus .1em minus .1emChromothripsis Rearrangements Are Informed by 3D-Genome Organization
	1 Introduction
	2 Materials and Methods
		2.1 Hi-C Data
		2.2 SVs Data
		2.3 Chromothripsis Rearrangements Data
		2.4 Breakpoints Pairwise Distances Analysis
		2.5 Statistical Analysis
	3 Results and Discussion
	4 Conclusions
	References
Metagenomics
Using Computational Synthetic Biology Tools to Modulate Gene Expression Within a Microbiome
	1 Introduction
	2 Methods
		2.1 Translation Efficiency Modeling
		2.2 Transcription Optimization
		2.3 Editing Restriction Site Presence
		2.4 Data Curation for In-SilicoAnalysis
		2.5 In-vitro Methods
	3 Results
		3.1 Editing Restriction Site Presence
		3.2 Translation Efficiency Modeling
		3.3 Transcription Optimization
		3.4 In-vitro Results
	4 Discussion
		4.1 Future Plans
		4.2 Applications
	References
Metagenomics Binning of Long Reads Using Read-Overlap Graphs
	1 Introduction
	2 Methods
		2.1 Step 1: Constructing Read-Overlap Graph
		2.2 Step 2: Obtaining Read Features
		2.3 Step 3: Performing Probabilistic Sampling
		2.4 Step 4: Detecting Clusters for Sampled Reads
		2.5 Step 5: Binning Remaining Reads by Inductive Learning
	3 Experimental Setup
		3.1 Simulated Datasets
		3.2 Real Datasets
		3.3 Baselines and Evaluation Criteria
	4 Results and Discussion
		4.1 Binning Results
		4.2 Assembly Results
	5 Implementation
	6 Conclusion
	A  Dataset Information
	B  Interpretation of AMBER Per-bin F1-Score
	References
A Mixed Integer Linear Programming Algorithm for Plasmid Binning
	1 Introduction
	2 Hybrid Approach for Plasmid Binning Using Mixed Integer Linear Programming
		2.1 Input: Contigs and the Assembly Graph
		2.2 PlasBin Workflow
		2.3 MILP Formulation
	3 Experimental Results
		3.1 Performance Comparison of Plasmid Binning Tools
		3.2 Comparison of PlasBin and HyAsP
		3.3 Computational Footprint
	4 Discussion
	References
Genomic Sequencing
Benchmarking Penalized Regression Methods in Machine Learning for Single Cell RNA Sequencing Data
	1 Introduction
	2 Methods
		2.1 Penalized Regression
		2.2 Clustering
		2.3 K-Fold Cross-validation
		2.4 ROC AUC
	3 Research Design and Data
		3.1 Experimental Data
		3.2 Research Design
	4 Results
	5 Discussion
	6 Conclusion and Future Work
	References
Deciphering the Tissue-Specific Regulatory Role of Intronless Genes Across Cancers
	1 Introduction
	2 Results
		2.1 Functional Assignment and Gene Expression of IGs in Normal Tissue
		2.2 IGs Tend to Have a More Induced Gene Expression Pattern When Compared to MEGs
		2.3 Upregulated IGs Across Cancer Types Encode for Highly Conserved HDAC Deacetylate Histones Involved in Negative Gene Regulation
		2.4 IG Downregulation Is Conserved in Breast and Colon Cancers and Is Involved in Signaling and Cell-Specific Functions
		2.5 Cancer-Specific Differentially Expressed IGs
		2.6 Proteins Encoded by Cancer-Specific Deregulated IGs Interact with Distinct Groups of Proteins in PPI Networks
		2.7 DE-IGs Participate in the Genetic ``rewiring'' of Cancer Cells
	3 Discussion
	4 Materials and Methods
		4.1 Data Extraction and Curation for IG, and MEG Datasets
		4.2 Gene Expression Profiles in Healthy Tissue Tissue
		4.3 Bipartite Network and Quantification of Shared and Unique DE-IGs
		4.4 Data Source and Differential Expression Analysis Across Cancer
		4.5 Upregulation Significant Differences of IGs and MEGs Among Cancers
		4.6 Functional Enrichment Analysis of Differentially Expressed IGs
		4.7 DE-IGs PPI Network Construction and Protein Complex Identification
		4.8 BRCA Network Deconvolution
	References
Author Index