Algorithms in Bioinformatics
11th International Workshop, WABI 2011, Saarbrücken, Germany, September 5-7, 2011, Proceedings
Published on 31. August 2011
XIII, 378 pages
978-3-642-23038-7 (ISBN)
Description
This book constitutes the refereed proceedings of the 11th International Workshop on Algorithms in Bioinformatics, WABI 2011, held in Saarbrücken, Germany, in September 2011.
The 30 papers presented were carefully reviewed and selected from 77 submissions. They cover aspects of algorithms in bioinformatics, computational biology and systems biology.
More details
Other editions
Additional editions
Teresa M. Przytycka | Marie-France Sagot
Algorithms in Bioinformatics
11th International Workshop, WABI 2011, Saarbrücken, Germany, September 5-7, 2011, Proceedings
Book
08/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Automated Segmentation of DNA Sequences with Complex Evolutionary Histories
- Introduction
- Algorithm
- Experiments
- Conclusion
- References
- Towards a Practical O(n log n) Phylogeny Algorithm
- Introduction
- Background and Related Work
- Definitions
- Summary of Our Previous Work
- Quartets
- Other Fast Phylogenetic Algorithms
- Quality Measures
- Extensions to Improve Performance
- Quartet Weights
- Biased Choice of Quartets
- Multiple Insertion Rounds
- Confidence Threshold
- Repeating the Random Walk
- As-Yet Unsuccessful Ideas
- Experiments
- Conclusion
- References
- A Mathematical Programming Approach to Marker-Assisted Gene Pyramiding
- Introduction
- Problem Definition and Complexity
- Method
- MIP Formulation
- Experimental Results
- Conclusion
- References
- Localized Genome Assembly from Reads to Scaffolds: Practical Traversal of the Paired String Graph
- Introduction
- Paired String Graph and Non-branching Paths
- Paired Assembly Problem
- Non-branching Paths in the Ideal Case
- Practical Non-branching Paths
- Results
- Discussion
- References
- Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstructions
- Introduction
- Background
- SR Functions for the Kimura 2-Parameter Model
- Deviation from Additivity in Homogeneous Substitution Models
- Performance of Non-additive SR Functions in Quartet Resolution
- Using Fisher's Linear Discriminant
- Inferring Trees from Genomic Sequences
- Discussion and Outlook
- References
- Constructing Large Conservative Supertrees
- Introduction
- Preliminaries
- Strict and Loose Supertrees
- ILP Formulations
- Formulations Based on the Restricted Span
- ILPs for Finding Good Splits
- A Divide-and-Conquer Heuristic
- Experimental Results
- Discussion
- References
- PepCrawler: A Fast RRT-Like Algorithm for High-Resolution Refinement and Binding-Affinity Estimation of Peptide Inhibitors
- References
- Removing Noise from Gene Trees
- Introduction
- Definitions
- Trees
- Reconciliation
- LCA Mapping
- Duplication Vertices and MD-trees
- Motivation and Problem Statement
- Method
- Uniquely Leaf-Labelled Gene Trees
- No AD above NAD
- An Algorithm for the General Case
- Results
- Conclusion
- References
- Boosting Binding Sites Prediction Using Gene's Positions
- Introduction
- PreCisIon: PREdiction of CIS-Regulatory Elements Improved by Gene's Position
- Individual Classifiers
- Classifier Fusion Using Boosting
- Results
- Comparison with Individual Classifiers
- Comparison with Other Classifiers Fusion Methods
- Functional Analysis of Predicted Targets of Global TFs
- Conclusion
- References
- Constructing Perfect Phylogenies and Proper Triangulations for Three-State Characters
- Introduction
- Notation and Prior Results
- Structure of Separators
- Conclusions and Further Work
- References
- On a Conjecture about Compatibility of Multi-states Characters
- Introduction
- Preliminaries
- Our Contributions
- The 4-States Characters Case
- A Closure Operation for Chordal Sandwich Problems
- Conclusion
- References
- Learning Protein Functions from Bi-relational Graph of Proteins and Function Annotations
- Introduction
- Bi-relational Graph Model
- Methods
- Experiments and Results
- Discussion and Conclusion
- References
- Graph-Based Decomposition of Biochemical Reaction Networks into Monotone Subsystems
- Introduction
- Monotone Systems
- Dynamic Network Models
- Directed Species-Reaction Graph
- Identification of Monotonicity
- Example Network
- Algorithm for Monotone Systems Decomposition
- Overview
- Phase 1: Initial Decomposition
- Phase 2: Assignment of Reaction Vertices
- Phase 3: Refinement of Decomposition
- Application Example
- Conclusion
- References
- Seed-Set Construction by Equi-entropy Partitioning for Efficient and Sensitive Short-Read Mapping
- Introduction
- Equi-entropy Partitioning Method
- Soft Seeds
- Partitioning Read into Seeds
- Entropy and Adjustment of Seed Lengths
- Computation of Entropy
- Bidirectional Search
- Equi-entropy Partitioning
- Adjusting Entropy Parameter H
- Experimental Results and Discussion
- Implementation Issues
- Performance Estimation Using Random Reads
- Performance Estimation Using Actual Biological Data
- Performance Comparison with BFAST and BWA
- Conclusion
- References
- A Practical Algorithm for Ancestral Rearrangement Reconstruction
- Introduction
- Methods
- Finding the Best History in a Neighbourhood
- Strategies for Proposing Candidates
- Unequal Gene Content
- Results
- Conclusion
- References
- Bootstrapping Phylogenies Inferred from Rearrangement Data
- Introduction
- Background
- Bootstrap and Jackknife
- Rearrangement Data
- Distance-Based Phylogeny Reconstruction from Rearrangement Data
- Robustness Estimation for Trees Reconstructed from Rearrangement Data
- Experimental Design
- Experimental Results and Analysis
- A Dataset of Vertebrate Genomes
- Discussion
- References
- Speeding Up Bayesian HMM by the Four Russians Method
- Introduction
- Hidden Markov Model
- Bayesian Analysis: Forward-Backward Gibbs Sampling
- Speeding Up MCMC
- Compression and Forward Variables
- Backward-Forward State Sequence
- Fast Sampling Algorithm
- Empirical Results
- Conclusion
- References
- Using Dominances for Solving the Protein Family Identification Problem
- Introduction
- DAST
- The Protein Family Identification Problem
- Dominance
- Modifying DAST for Using Dominance
- Notation and Definitions
- Maximum Clique Formulation of DAST
- Bounding Strategy
- Computational Results
- DAST on Skolnick Set
- DASTb versus A_purva on SHREC'10 Set
- Conclusion and Future Work
- References
- Maximum Likelihood Estimation of Incomplete Genomic Spectrum from HTS Data
- Introduction
- Virtual String Expectation Maximization
- Experimental Validation of IsoVSEM on RNA-Seq Data
- VSEM Enhancement of ViSpA
- Experimental Validation of ViSpA-VSEM on Simulated Data
- Conclusions and Future Works
- References
- Algorithm for Identification of Piecewise Smooth Hybrid Systems: Application to Eukaryotic Cell Cycle Regulation
- Introduction
- Hybrid Models
- Regulated Reaction Graphs and Hybrid Reaction Schemes
- Identification of Piecewise Smooth Models
- Examples
- Conclusion
- References
- Parsimonious Reconstruction of Network Evolution
- Introduction
- A Framework for Representing Network Histories
- Parsimonious Reconstruction of a Network History
- A Fast Heuristic Algorithm
- Removing Blocking Loops
- Reconstruction of a Common Ancestor of Two Graphs
- Modifications for Self-loops
- Modifications for Directed Graphs
- Results
- Generating Plausible Simulated Histories
- Reconstructing Histories
- Conclusion
- References
- A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms
- Introduction
- Notations and Key Notions
- Generic Problems and Algorithms for F-Paths in F-Graphs
- F-Graphs Reformulation of (Pseudoknotted) RNA Conformation Spaces
- Foreword: Shortening Correctness Proofs through Generating Functions
- RNA Secondary Structures
- Simple-Type Pseudoknots
- Fully-Recursive Kissing Hairpins
- Extending the Framework: Extraction of Moments and Exact Correlations
- Conclusion and Perspectives
- References
- Indexing Finite Language Representation of Population Genotypes
- Introduction
- Definitions
- Compressed Indexes
- Burrows-Wheeler Transform for Finite Languages
- Basic Navigation
- Searching
- Analysis
- Index Construction
- Implementation and Experiments
- Discussion
- References
- Efficiently Solvable Perfect Phylogeny Problems on Binary and k-State Data with Missing Values
- Introduction and Background
- Enumerating Fully Labeled Phylogenetic Trees
- Generalizing the Rich Data Hypothesis
- The Generalized Rich Data Hypothesis
- Finding m-Cliques
- Directed Binary Partial Characters
- Empirical Results and Discussion
- References
- Separating Metagenomic Short Reads into Genomes via Clustering
- Introduction
- Methods
- Preliminaries
- Finding Unique l-Mers
- Clustering the Unique l-Mers
- Merging Clusters and the Final Clustering of Metagenomic Reads
- Handling Genomes with Arbitrary Abundance Levels
- Experimental Results
- Simulated Data Sets
- Performance Evaluation
- Experiments on Genomes Separated by Different Phylogenetic Distances
- Handling Sequencing Errors
- The Issue of Abundance Levels
- Comparison with CompostBin
- Performance on a Real Dataset
- Implementation and Future Work
- References
- Finding Driver Pathways in Cancer: Models and Algorithms
- Introduction
- Our Contribution
- Stochastic Models for Somatic Mutations in Cancer
- Finding Recurrently Mutated Genes
- A Weight Function to Identify Driver Pathways
- Experimental Results
- Conclusions
- References
- Clustering with Overlap for Genetic Interaction Networks via Local Search Optimization
- Introduction
- Methods
- CLOVER Cost Function
- Local Search Algorithm
- Results
- Genetic Interaction Data Sets
- Evaluation on Genetic Interactions Networks
- Evaluation of Clusters
- Evaluation of Overlaps
- Future Improvements
- References
- Dynamic Programming Algorithms for Efficiently Computing Cosegmentations between Biological Images
- Introduction
- Problem Formulation
- A Quasi-Linear Time Algorithm for Computing Overlap Weights
- Dynamic Programming Algorithm for Constrained Tree Assignment
- Results
- Conclusion and Future Work
- References
- GASTS: Parsimony Scoring under Rearrangements
- Introduction
- Rearrangements and Phylogenetic Analysis
- A Heuristic for Multichromosomal Medians
- Initialization with Adequate Subgraphs
- Weighted Adjacencies and a Weighting Schema
- Using the Generalized Adequate Subgraphs
- Testing Our New Tree-Scoring Method
- Ancestral Genome Reconstruction
- Phylogenetic Reconstruction
- Applications on Real Data
- Conclusion
- References
- OMG! Orthologs in Multiple Genomes - Competing Graph-Theoretical Formulations
- Introduction
- The Competing Formulations and Their Algorithms
- Minimum Weight Orthogonal Partition (MWOP)
- Minimize Singleton Vertices (MISIV)
- Maximum Edges in Transitive Closure (MEC)
- Issues of Accuracy, Deliberate Bias and Interpretation
- Application to 10 Plant Genomes
- Percolation, Tangles and Run Time
- Results
- Conclusions
- References
- Author Index
