This book constitutes the refereed proceedings of the 5th International Workshop on Algorithms in Bioinformatics, WABI 2005, held in Mallorca, Spain, in September 2005 as part of the ALGO 2005 conference meetings.
The 34 revised full papers presented were carefully reviewed and selected from 95 submissions. All current issues of algorithms in bioinformatics are addressed with special focus on statistical and probabilistic algorithms in the field of molecular and structural biology. The papers are organized in topical sections on expression (hybrid methods and time patterns), phylogeny (quartets, tree reconciliation, clades and haplotypes), networks, genome rearrangements (transposition model and other models), sequences (strings, multi-alignment and clustering, clustering and representation), and structure (threading and folding).
Author(s): Nora Speer, Christian Spieth, Andreas Zell (auth.), Rita Casadio, Gene Myers (eds.)
Series: Lecture Notes in Computer Science 3692 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 436
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Computation by Abstract Devices; Discrete Mathematics in Computer Science; Probability and Statistics in Computer Science; Bioinformatics
Front Matter....Pages -
Spectral Clustering Gene Ontology Terms to Group Genes by Function....Pages 1-12
Dynamic De-Novo Prediction of microRNAs Associated with Cell Conditions: A Search Pruned by Expression....Pages 13-26
Clustering Gene Expression Series with Prior Knowledge....Pages 27-38
A Linear Time Biclustering Algorithm for Time Series Gene Expression Data....Pages 39-52
Time-Window Analysis of Developmental Gene Expression Data with Multiple Genetic Backgrounds....Pages 53-64
A Lookahead Branch-and-Bound Algorithm for the Maximum Quartet Consistency Problem....Pages 65-76
Computing the Quartet Distance Between Trees of Arbitrary Degree....Pages 77-88
Using Semi-definite Programming to Enhance Supertree Resolvability....Pages 89-103
An Efficient Reduction from Constrained to Unconstrained Maximum Agreement Subtree....Pages 104-115
Pattern Identification in Biogeography....Pages 116-127
On the Complexity of Several Haplotyping Problems....Pages 128-139
A Hidden Markov Technique for Haplotype Reconstruction....Pages 140-151
Algorithms for Imperfect Phylogeny Haplotyping (IPPH) with a Single Homoplasy or Recombination Event....Pages 152-164
A Faster Algorithm for Detecting Network Motifs....Pages 165-177
Reaction Motifs in Metabolic Networks....Pages 178-191
Reconstructing Metabolic Networks Using Interval Analysis....Pages 192-203
A 1.375-Approximation Algorithm for Sorting by Transpositions....Pages 204-215
A New Tight Upper Bound on the Transposition Distance....Pages 216-227
Perfect Sorting by Reversals Is Not Always Difficult....Pages 228-238
Minimum Recombination Histories by Branch and Bound....Pages 239-250
A Unifying Framework for Seed Sensitivity and Its Application to Subset Seeds....Pages 251-263
Generalized Planted ( l , d )-Motif Problem with Negative Set....Pages 264-275
Alignment of Tandem Repeats with Excision, Duplication, Substitution and Indels (EDSI)....Pages 276-290
The Peres-Shields Order Estimator for Fixed and Variable Length Markov Models with Applications to DNA Sequence Similarity....Pages 291-302
Multiple Structural RNA Alignment with Lagrangian Relaxation....Pages 303-314
Faster Algorithms for Optimal Multiple Sequence Alignment Based on Pairwise Comparisons....Pages 315-327
Ortholog Clustering on a Multipartite Graph....Pages 328-340
Linear Time Algorithm for Parsing RNA Secondary Structure....Pages 341-352
A Compressed Format for Collections of Phylogenetic Trees and Improved Consensus Performance....Pages 353-364
Optimal Protein Threading by Cost-Splitting....Pages 365-375
Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment....Pages 376-388
Rotamer-Pair Energy Calculations Using a Trie Data Structure....Pages 389-400
Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity....Pages 401-413
The Main Structural Regularities of the Sandwich Proteins....Pages 414-422
Discovery of Protein Substructures in EM Maps....Pages 423-434
Back Matter....Pages -
