Algorithms for Computational Biology: 8th International Conference, AlCoB 2021, Missoula, MT, USA, June 7–11, 2021, Proceedings

Preface
Organization
Contents
Biological Dynamical Systems and Other Biological Processes
Learning Molecular Classes from Small Numbers of Positive Examples Using Graph Grammars
	1 Introduction
	2 Related Work
	3 Learning the Graph Grammar
		3.1 Learning a Graph-Grammar
	4 Experiments
		4.1 Comparison to Machine Learning on SMILES
		4.2 Comparison to Standard Machine Learning Using Graph-Grammar Rules as Features
	5 Conclusion
	References
Can We Replace Reads by Numeric Signatures? Lyndon Fingerprints as Representations of Sequencing Reads for Machine Learning
	1 Introduction
	2 Lyndon Factorizations and Overlapping Reads
	3 Probabilistic Behaviour of Fingerprints
	4 Methodology and Experiments
		4.1 Fingerprint-Based Approach
		4.2 k-Finger-Based Approach
	5 Discussion
	References
Exploiting Variable Sparsity in Computing Equilibria of Biological Dynamical Systems by Triangular Decomposition
	1 Introduction
	2 Preliminaries
		2.1 Autonomous Biological Dynamical Systems and Their Equilibria
		2.2 Polynomial Sets and Associated Graphs
		2.3 Triangular Sets and Sparse Triangular Decomposition
	3 Variable Sparsity in Biological Dynamical Systems
		3.1 Original Variable Sparsity
		3.2 Variable Sparsity After Chordal Completion
	4 Sparse Triangular Decomposition for Computing Equilibria
	5 Concluding Remarks
	References
A Recovery Algorithm and Pooling Designs for One-Stage Noisy Group Testing Under the Probabilistic Framework
	1 Introduction
	2 Methods
		2.1 Noisy Group Testing Under the Probabilistic Framework
		2.2 A Group Testing Protocol
		2.3 Recovery Algorithm
	3 Results
		3.1 Performance of the Recovery Algorithm
		3.2 Pooling Matrices
	4 Discussion
	References
Phylogenetics
Novel Phylogenetic Network Distances Based on Cherry Picking
	1 Introduction
	2 Preliminaries
		2.1 Network Definitions
		2.2 Cherry Operations
	3 Distances Based on Cherry-Picking Sequences
	4 Computing the Tail Distance Between Two Trees
		4.1 Computing an LR-MAST
	5 NP-hardness of dtail Between a Tree and a Network
	6 Discussion and Future Work
	1 Proof of Lemma 1 (Page 6)
	2 Proof of Theorems in Sect.3 (Theorem 2 Page 7, Theroem 3 Page 8, Theorem 4 Page 8, Theorem 5 Page 8)
	3 Proof of Lemma 6, 7 and Theorem 8 (Page 9)
	4 LR-MAST Algorithm, and Associated Theorem (Page 9)
	5 Proof of Theorem 10 (Page 12) and Theorem 11 (Page 12)
	References
Best Match Graphs with Binary Trees
	1 Introduction
	2 Best Match Graphs
	3 Binary Trees Explaining a BMG in Near Cubic Time
	4 The Binary-Refinable Tree of a BMG
	5 Simulation Results
	6 Concluding Remarks
	References
Scalable and Accurate Phylogenetic Placement Using pplacer-XR
	1 Introduction
	2 pplacer-XR
	3 Experimental Study Design
	4 Results
		4.1 Query Placement Accuracy
		4.2 Time Analysis
	5 Conclusions
	References
Comparing Methods for Species Tree Estimation with Gene Duplication and Loss
	1 Introduction
	2 Experimental Design
	3 Results
	4 Discussion and Conclusion
	References
Sequence Alignment and Genome Rearrangement
Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information
	1 Introduction
	2 Background
	3 Labeled Intergenic Breakpoint Graph
	4 3-Approximation Algorithm
	5 Conclusions
	References
Reversals Distance Considering Flexible Intergenic Regions Sizes
	1 Introduction
	2 Definitions
		2.1 Flexible Weighted Cycle Graph
	3 Results
		3.1 Lower Bound
		3.2 Approximation Algorithm
	4 Conclusion
	References
Improved DNA-versus-Protein Homology Search for Protein Fossils
	1 Introduction
	2 Methods
		2.1 Alignment Elements
		2.2 Scoring Scheme
		2.3 Finding a Maximum-Score Local Alignment
		2.4 Probability Model
		2.5 Sum over All Alignments Passing Through (i,j)
		2.6 Significance Calculation
		2.7 Seed-and-Extend Heuristic
		2.8 Fitting Substitution and Gap Parameters to Sequence Data
	3 Results
		3.1 Software
		3.2 Parameter Fitting
		3.3 Significance Calculation and Simple Sequences
		3.4 Comparison to Blastx
		3.5 Discovery of Missing TE Orders in the Human Genome
	4 Discussion
	References
The Maximum Weight Trace Alignment Merging Problem
	1 Introduction
	2 Maximum Weight Trace Alignment Merging
	3 Graph Clustering Merger (GCM)
	4 Experimental Study
	5 Results
	6 Conclusions
	References
Author Index