Algorithms for Computational Biology: 4th International Conference, AlCoB 2017, Aveiro, Portugal, June 5-6, 2017, Proceedings (Lecture Notes in Computer Science Book 10252)

This book constitutes the proceedings of the 4th InternationalConference on Algorithms for Computational Biology, AlCoB 2017, held in Aveiro, Portugal, in June 2017. The 10 full papers presented together with 2 invited papers were carefully reviewed and selected from 24 submissions. They are organized in the following topical sections: Graph Algorithms for Computational Biology; Phylogenetics; and Sequence Analysis and Other Biological Processes. Preface 6 Organization 7 Contents 9 Invited Talks 11 Biomedical Applications of Prototype Based Classifiers and Relevance Learning 12 1 Introduction 12 2 Distance-based Classification and Prototypes 13 2.1 Nearest Prototype Classifiers 13 2.2 Learning Vector Quantizaton 15 2.3 Alternative Distances 16 2.4 Adaptive Distances and Relevance Learning 18 2.5 Generalized Matrix Relevance Learning 18 2.6 Related Schemes and Variants of GMLVQ 19 3 Biomedical Applications of GMLVQ 21 3.1 Steroid Metabolomics in Endocrinology 21 3.2 Cytokine Markers in Inflammatory Diseases 23 3.3 Recurrence Risk Prediction in Clear Cell Renal Cell Carcinoma 25 3.4 Further Bio-medical and Life Science Applications 27 4 Concluding Remarks 28 References 28 Describing the Local Structure of Sequence Graphs 33 1 Background 33 2 The Challenges of Defining Sites on Graphs 34 3 Mathematical Background 35 3.1 Directed and Bidirected Sequence Graphs 35 3.2 Bubbles, Superbubbles, Ultrabubbles and Snarls 36 4 Graphs Which Are Decomposable into Nested Simple Sites 39 4.1 Traversals and Subpaths 39 4.2 Simple Bubbles and Nested Simple Bubbles 40 4.3 A Partial Taxonomy of Graph Notifs Which Do Not Admit Decomposition into Sites 42 4.4 The Relationship Between Nested Simple Sites and Series Parallel Graphs 43 5 Abutting Variants 44 5.1 Bundles 44 5.2 An Algorithm for Bundle-Finding 46 5.3 Bundles and Snarl Boundaries 49 5.4 Defining Sites Using Bundles 49 5.5 Bundles Containing Deletions 50 6 Discussion 54 References 55 Graph Algorithms for Computational Biology 56 Mapping RNA-seq Data to a Transcript Graph via Approximate Pattern Matching to a Hypertext 57 1 Introduction 57 2 Preliminaries 59 3 Methods 60 4 Experimental Analysis 63 5 Conclusions 68 References 68 A Fast Algorithm for Large Common Connected Induced Subgraphs 70 1 Introduction 70 2 Methods 74 3 Results 76 4 Implementation 79 References 81 Ranking Vertices for Active Module Recovery Problem 83 1 Introduction 83 2 Methods 84 2.1 Formal Definitions 84 2.2 Optimal-on-Average Ranking 85 2.3 Semi-heuristic Ranking 86 2.4 Baseline Methods 87 3 Experimental Results 88 3.1 Small Graphs 88 3.2 Medium-Sized Graphs 89 3.3 Large Real-World Graph 89 3.4 Generating Graphs for Experiments 91 4 Conclusion 91 References 92 Computational Processes that Appear to Model Human Memory 93 1 Introduction 93 2 Sets, Relations, and Closure 94 2.1 Relationships 94 2.2 Closure 96 2.3 Neighborhood Closure 96 3 Irreducible Networks 96 4 Computing Similar Networks 99 5 Biological Memory 100 5.1 Role of Closure 100 5.2 Role of Chordless Cycles 102 A Appendix 103 References 105 Phylogenetics 108 Inferring the Distribution of Fitness Effects (DFE) of Newly-Arising Mutations Using Samples Taken from Evolving Populations in Real Time 109 1 Introduction 109 1.1 Previous Studies 110 1.2 Evolution and the DFE 110 1.3 The Present Study 111 2 Fitness Evolution 112 2.1 Evolution of the Distribution of Fitnesses 112 2.2 Evolution of the Corresponding Characteristic Function 112 2.3 Dynamics of Mean Fitness 112 2.4 Dynamics of Fitness Variance and Higher Cumulants 113 2.5 Connection to Classical Theory 113 3 Parametric Estimation of the DFE 113 3.1 Integral Method 114 3.2 Derivative Method of DFE Estimation 114 4 Non-parametric Distance Measures for DFEs 115 4.1 Conjecture 115 4.2 Mahalanobis-Based Distance Measures 116 4.3 Norm-Based Distance Measures 117 5 Simulation Tests 117 5.1 Fitness Dynamics 117 5.2 Reconstructing the DFE and Estimating U 118 5.3 Reconstructing DFE Dynamics 118 References 120 An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees 121 1 Introduction 121 2 Problem Definitions 122 3 The New Algorithm 124 3.1 Counting Common Resolved Triplets in N1 and N2 125 3.2 Counting Common Fan Triplets in N1 and N2 129 4 Concluding Remarks 131 References 132 Clustering the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model 133 1 Introduction 133 2 Definitions 135 2.1 Maximum Parsimony Reconciliations 135 2.2 Reconciliation Graphs 136 3 Clustering Reconciliation Space 138 3.1 k-medoids 139 3.2 k-centers 141 4 Computing the Reconciliation Count Function 142 5 Conclusion 144 References 144 Sequence Analysis and Other Biological Processes 146 CSA-X: Modularized Constrained Multiple Sequence Alignment 147 1 Introduction 147 2 Methods 149 3 Method of Assessments 151 3.1 Accuracy, Statistical Significance and Parameters 153 4 Results 154 4.1 Comparison of CSA-X with RE-MuSiC 154 4.2 Comparison of CSA-X with the Underlying MSA Program 155 4.3 Statistical Analysis 155 5 Conclusions 157 References 157 Quantifying Information Flow in Chemical Reaction Networks 159 1 Introduction 159 2 Stochastic Simulation and Flux Analysis 161 3 Refining the Stochastic Flux Analysis Algorithm 163 4 Flux Paths 165 5 A Case Study: Gemcitabine 167 6 Discussion 169 References 170 Parallel Biological Sequence Comparison in Linear Space with Multiple Adjustable Bands 171 1 Introduction 171 2 Biological Sequence Comparison 172 2.1 Basic Algorithms - NW and SW 172 2.2 NW and SW Variants 173 3 Design of CUDAlign 4.0 175 4 Design of Fickett-MM 177 5 Experimental Results 179 6 Conclusion 182 References 182 Author Index 184 Front Matter....Pages I-X Front Matter....Pages 1-1 Biomedical Applications of Prototype Based Classifiers and Relevance Learning....Pages 3-23 Front Matter....Pages 47-47 Mapping RNA-seq Data to a Transcript Graph via Approximate Pattern Matching to a Hypertext....Pages 49-61 Ranking Vertices for Active Module Recovery Problem....Pages 75-84 Computational Processes that Appear to Model Human Memory....Pages 85-99 Front Matter....Pages 101-101 Inferring the Distribution of Fitness Effects (DFE) of Newly-Arising Mutations Using Samples Taken from Evolving Populations in Real Time....Pages 103-114 An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees....Pages 115-126 Clustering the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model....Pages 127-139 Front Matter....Pages 141-141 CSA-X: Modularized Constrained Multiple Sequence Alignment....Pages 143-154 Quantifying Information Flow in Chemical Reaction Networks....Pages 155-166 Parallel Biological Sequence Comparison in Linear Space with Multiple Adjustable Bands....Pages 167-179 Back Matter....Pages 181-181