Algorithms for computational biology : 8th international conference, AlCoB 2021, Missoula, MT, USA, June 7-11, 2021 : proceedings

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 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 This book constitutes the proceedings of the 8th International Conference on Algorithms for Computational Biology, AlCoB 2020, was planned to be held in Missoula, MT, USA in June 2021. Due to the Covid-19 pandemic, AlCoB 2020 and AlCoB 2021 were merged and held on these dates together. AlCoB 2020 proceedings were published as LNBI 12099. The 12 full papers included in this volume were carefully reviewed and selected from 22 submissions. They were organized in topical sections on genomics, phylogenetics, and RNA-Seq and other biological processes. The scope of AlCoB includes topics of either theoretical or applied interest, namely: sequence analysis; sequence alignment; sequence assembly; genome rearrangement; regulatory motif finding; phylogeny reconstruction; phylogeny comparison; structure prediction; compressive genomics; proteomics: molecular pathways, interaction networks, mass spectrometry analysis; transcriptomics: splicing variants, isoform inference and quantification, differential analysis; next-generation sequencing: population genomics, metagenomics, metatranscriptomics, epigenomics; genome CD architecture; microbiome analysis; cancer computational biology; and systems biology.