LEADER 12854nam 22008415 450 001 996200356903316 005 20200706033526.0 010 $a3-662-48221-5 024 7 $a10.1007/978-3-662-48221-6 035 $a(CKB)3890000000001397 035 $a(SSID)ssj0001558439 035 $a(PQKBManifestationID)16184102 035 $a(PQKBTitleCode)TC0001558439 035 $a(PQKBWorkID)14819100 035 $a(PQKB)11666122 035 $a(DE-He213)978-3-662-48221-6 035 $a(MiAaPQ)EBC6301167 035 $a(MiAaPQ)EBC5585379 035 $a(Au-PeEL)EBL5585379 035 $a(OCoLC)919495013 035 $a(PPN)188460675 035 $a(EXLCZ)993890000000001397 100 $a20150827d2015 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms in Bioinformatics$b[electronic resource] $e15th International Workshop, WABI 2015, Atlanta, GA, USA, September 10-12, 2015, Proceedings /$fedited by Mihai Pop, Hélène Touzet 205 $a1st ed. 2015. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2015. 215 $a1 online resource (XX, 328 p. 85 illus.) 225 1 $aLecture Notes in Bioinformatics ;$v9289 300 $aIncludes index. 311 $a3-662-48220-7 327 $aIntro -- Preface -- Organization -- Abstracts -- Reference-free Compression of High Throughput Sequencing Data with a Probabilistic de Bruijn Graph -- Genome Scaffolding with PE-Contaminated Mate-Pair Libraries -- Network Properties of the Ensemble of RNA Structures -- Contents -- BicNET: Efficient Biclustering of Biological Networks to Unravel Non-Trivial Modules -- 1 Introduction -- 2 Background -- 3 Solution -- 3.1 Network Modules with Flexible Coherency -- 3.2 BicNET: Efficient Biclustering of Biological Networks -- 4 Results and Discussion -- 4.1 Results on Synthetic Data -- 4.2 Results on Real Data -- 5 Conclusions and Future Work -- References -- Simultaneous Optimization of both Node and Edge Conservation in Network Alignment via WAVE -- 1 Introduction -- 1.1 Motivation -- 1.2 Related Work -- 1.3 Our Contributions and Significance -- 2 Methods -- 2.1 Data -- 2.2 Combining Topological and Sequence Information Within NCF -- 2.3 Evaluation of Alignment Quality -- 2.4 Our Methodology -- 3 Results and Discussion -- 3.1 Comparison of Edge-Weighted and Edge-Unweighted Versions of WAVE -- 3.2 Comparison of Different Parameter Values Within WAVE -- 3.3 Comparison of Five NCF-AS Methods -- 3.4 Comparison of WAVE with Very Recent Methods -- 4 Concluding Remarks -- A Appendix -- A.1 Appendix Figures -- References -- The Topological Profile of a Model of Protein Network Evolution Can Direct Model Improvement -- 1 Introduction -- 2 Methods -- 2.1 The Evolutionary Model -- 2.2 The Empirical Network -- 2.3 Topological Measures Assessed -- 3 Results -- 3.1 Success of Driving Properties Towards the Empirical Topology -- 3.2 Non-Optimized Topological Properties that Trend Towards Empirical Values -- 3.3 Variability of Topological Measures -- 3.4 Correlation Among Topological Characteristics -- 3.5 Improving the Evolutionary Model -- 4 Conclusion. 327 $aReferences -- Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-Viral Infection Patterns -- 1 Introduction -- 2 Regular Tree Grammars and Curry-Encoding -- 3 The RTG Network Parse-and-Search Problem -- 4 Algorithms for Solving Problem 2 -- 4.1 Stage 1: Hypergraph Construction and Its Optimal Derivation -- 4.2 Stage 2: Computing K-Best Scoring Trees -- 5 Results -- 6 Discussion -- References -- Orthology Relation and Gene Tree Correction: Complexity Results -- 1 Introduction -- 2 Trees and Orthology Relations -- 2.1 Evolution of a Gene Family -- 2.2 Relation Graph -- 3 Relation Correction Problems -- 3.1 The Minimum Edge-Removal Consistency Problem -- 3.2 The Minimum Node-Removal Consistency Problem -- 4 Gene Tree Correction Problems -- 4.1 The Maximum Homology Correction Problem -- 4.2 The Maximum Clade Correction Problem -- 5 Algorithmic Avenues -- 6 Conclusion -- References -- Finding a Perfect Phylogeny from Mixed Tumor Samples -- 1 Introduction -- 2 Problem Formulation -- 3 A Characterization of Row-Conflict Graphs -- 4 Complexity Results -- 5 An Algorithm for the Case When No Column Is Contained in both Columns of a Pair of Conflicting Columns -- 6 Discussion -- References -- A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies -- 1 Background -- 2 Methodology -- 2.1 The Number of Mapping Sites Required for Each Parasite Node -- 2.2 Space Complexity Reduction -- 2.3 Time Complexity Reduction -- 3 Results and Discussion -- 3.1 Analysis of Space Complexity Improvements (Synthetic Data) -- 3.2 Analysis of Time Complexity Improvements (Synthetic Data) -- 3.3 Time and Space Complexity Improvements for Biological Data -- References -- Maximum Parsimony Analysis of Gene Copy Number Changes -- 1 Introduction -- 2 Methods. 327 $a2.1 The Rectilinear Steiner Minimum Tree (RSMT) Problem -- 2.2 The Maximum Parsimony Tree (MPT) Problem -- 2.3 From MPT to RSMT -- 3 Experimental Results -- 3.1 Real Cancer Datasets -- 3.2 Simulated Cancer Data -- 4 Discussion -- References -- Multiple-Ancestor Localization for Recently Admixed Individuals -- 1 Introduction -- 2 Materials and Methods -- 2.1 Estimation of Spatial Parameters from Training Data -- 2.2 Localization of Individuals of 1-Generation Admixture -- 2.3 A Spatial Model for Individuals of g-generations Admixture -- 2.4 Simulation Setup -- 2.5 Method Comparison -- 3 Results -- 3.1 Localization of Simulated 1-Generation Admixed Individuals -- 3.2 Localization of Real Europeans from the POPRES Dataset -- 3.3 Localization of Simulated g-generation Admixed Individuals -- 4 Discussion -- References -- Association Mapping for Compound Heterozygous Traits Using Phenotypic Distance and Integer Programming -- 1 Biological Background and CH-Model -- 1.1 A Formal Model of a CH-trait at a Single Gene -- 2 The Phenotypic Distance Problem -- 2.1 An ILP Formulation for the Phenotypic Distance Problem -- 3 Simulated Data -- 4 The Most Striking and Positive Empirical Results -- 4.1 Speeding Up the Computations for Non-causal Genes and Permuted Data -- References -- Semi-nonparametric Modeling of Topological Domain Formation from Epigenetic Data -- 1 Introduction -- 1.1 Additional Related Work -- 2 The nTDP Model -- 2.1 The Likelihood Function -- 2.2 Nonparametric Form of the Effect Functions -- 3 Optimal Algorithms for Training and Inference -- 3.1 Training -- 3.2 Training Extensions -- 3.3 Inferring Domains Using the Trained Model -- 4 Results -- 4.1 Experimental Setup -- 4.2 nTDP Finds a Small Subset of Modifications Predictive of TADs -- 4.3 Predicting TADs from Histone Marks in Human -- 4.4 Multiscale Analysis of the Predicted TADs. 327 $a5 Conclusion -- References -- Scrible: Ultra-Accurate Error-Correction of Pooled Sequenced Reads -- 1 Introduction -- 2 Preliminaries -- 2.1 Pooling Design -- 2.2 Read Decoding -- 3 Methods -- 3.1 Indexing k-mers -- 3.2 Identification and Correction of Sequencing Errors -- 4 Experimental Results -- 4.1 Results on Synthetic Reads for the Rice Genome -- 4.2 Results on Real Reads from the Barley Genome -- References -- Jabba: Hybrid Error Correction for Long Sequencing Reads Using Maximal Exact Matches -- 1 Introduction -- 1.1 Related Work -- 2 Methods -- 2.1 Overview -- 2.2 Correction of the de Bruijn Graph -- 2.3 Aligning Reads to a de Bruijn Graph -- 3 Results Concerning Maximal Exact Matches -- 3.1 Coverage by Exact Regions -- 3.2 Occurrence of Exact Regions -- 3.3 Applications -- 4 Results -- 4.1 Data -- 4.2 Parameters -- 4.3 Evaluation Metrics -- 4.4 Evaluation -- References -- Optimizing Read Reversals for Sequence Compression -- 1 Introduction -- 2 Problem Taxonomy -- 3 Hardness Results -- 4 Approximation Algorithms -- 4.1 Approximations Based on TSP -- 4.2 Ordering with Reversals for Palindromic Value Functions -- 5 Experimental Results -- References -- Circular Sequence Comparison with q-grams -- 1 Introduction -- 2 Definitions and Properties -- 3 Algorithms -- 3.1 Algorithm hCSC: a Heuristic Algorithm -- 3.2 Algorithm saCSC: an Exact Suffix-Array-based Algorithm -- 4 Experimental Results -- 4.1 Accuracy -- 4.2 Time Performance -- 4.3 Application to Real Data -- 5 Final Remarks -- References -- Bloom Filter Trie -- A Data Structure for Pan-Genome Storage -- 1 Introduction -- 2 Existing Approaches -- 2.1 Data Structures -- 2.2 Software for Pan-Genome Storage -- 3 The Bloom Filter Trie -- 3.1 Uncompressed Container -- 3.2 Compressed Container -- 4 Operations Supported by the Bloom Filter Trie -- 4.1 Look-Up -- 4.2 Insertion. 327 $a4.3 Color Compression -- 5 Traversing Successors and Predecessors -- 6 Evaluation -- 7 Conclusion -- References -- A Filtering Approach for Alignment-Free Biosequences Comparison with Mismatches -- 1 Introduction -- 2 Preliminaries -- 2.1 Related Work -- 3 The MissMax Algorithm -- 3.1 Initial Set Up: MaxCork(1) -- 3.2 Minimum MaxCork from the Previous Step -- 3.3 Potential Candidates from the Previous Step -- 3.4 Theoretical and Practical Considerations -- 4 Preliminary Experimental Analysis -- 5 Concluding Remarks -- References -- Models and Algorithms for Genome Rearrangement with Positional Constraints -- 1 Introduction -- 1.1 Genomes as Sets of Signed Integers -- 1.2 DCJ and Sorting DCJs -- 1.3 The Minimum Weighted Rearrangements Problem -- 1.4 Positional Constraints as Colored Adjacencies -- 1.5 Locality and the Adjacency Graph -- 1.6 A Positional Weight Function -- 2 Minimum Local Parsimonious Scenario -- 2.1 Colored Partitions -- 2.2 Even-length Paths -- 3 Conclusion -- References -- Sparse RNA Folding Revisited: Space-Efficient Minimum Free Energy Prediction -- 1 Introduction -- 2 Time and Space Efficient Computation of the MFE -- 2.1 Time and Space Efficient Bp-Based Folding -- 2.2 Time and Space Efficient Calculation of the MFE -- 2.3 The Difficulty of MFE Fold Reconstruction Compared to Bp-Based Folding -- 3 MFE Folding with Fold Reconstruction -- 3.1 Adding Trace Arrows -- 3.2 Avoiding Trace Arrows -- 3.3 Garbage Collecting Trace Arrows -- 3.4 Algorithm Summary -- 3.5 Complexity -- 4 Empirical Results -- 5 Conclusion and Future Work -- References -- A Sparsified Four-Russian Algorithm for RNA Folding -- 1 Introduction -- 2 Problem Definition and Basic Algorithm -- 2.1 Extending the Notation and Moving Towards a Vector by Vector Computation of -- 3 Sparsification of the SSF Algorithm -- 3.1 OCT and STEP Sub-instances of Sequence. 327 $a4 On-demand Four Russians Speedup. 330 $aThis book constitutes the refereed proceedings of the 15th International Workshop on Algorithms in Bioinformatics, WABI 2015, held in Atlanta, GA, USA, in September 2015. The 23 full papers presented were carefully reviewed and selected from 56 submissions. The selected papers cover a wide range of topics from networks to phylogenetic studies, sequence and genome analysis, comparative genomics, and RNA structure. 410 0$aLecture Notes in Bioinformatics ;$v9289 606 $aBioinformatics 606 $aAlgorithms 606 $aComputer science?Mathematics 606 $aData mining 606 $aProteins  606 $aComputational Biology/Bioinformatics$3https://scigraph.springernature.com/ontologies/product-market-codes/I23050 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 606 $aData Mining and Knowledge Discovery$3https://scigraph.springernature.com/ontologies/product-market-codes/I18030 606 $aProtein Structure$3https://scigraph.springernature.com/ontologies/product-market-codes/L14050 615 0$aBioinformatics. 615 0$aAlgorithms. 615 0$aComputer science?Mathematics. 615 0$aData mining. 615 0$aProteins . 615 14$aComputational Biology/Bioinformatics. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aData Mining and Knowledge Discovery. 615 24$aProtein Structure. 676 $a572.80285 702 $aPop$b Mihai$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aTouzet$b Hélène$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996200356903316 996 $aAlgorithms in Bioinformatics$9772095 997 $aUNISA