This book constitutes the refereed proceedings of the 6th International Workshop on Algorithms in Bioinformatics, WABI 2006, held in Zurich, Switzerland in September 2006 in the course of the ALGO 2006 conference meetings.
The 36 revised full papers presented were carefully reviewed and selected from 100 submissions. All current issues of algorithms in bioinformatics are addressed, ranging from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. The papers deal with numerous biological problems, including genetic mapping, sequence alignment and sequence analysis, phylogeny, comparative genomics, and protein structure. For the first time, coverage extends to machine-learning approaches along with combinatorial optimization.
Author(s): Markus T. Friberg, Pedro Gonnet, Yves Barral (auth.), Philipp Bücher, Bernard M. E. Moret (eds.)
Series: Lecture Notes in Computer Science 4175 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 402
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Structures; Discrete Mathematics in Computer Science; Probability and Statistics in Computer Science; Bioinformatics
Front Matter....Pages -
Measures of Codon Bias in Yeast, the tRNA Pairing Index and Possible DNA Repair Mechanisms....Pages 1-11
Decomposing Metabolomic Isotope Patterns....Pages 12-23
A Method to Design Standard HMMs with Desired Length Distribution for Biological Sequence Analysis....Pages 24-31
Efficient Model-Based Clustering for LC-MS Data....Pages 32-43
A Bayesian Algorithm for Reconstructing Two-Component Signaling Networks....Pages 44-55
Linear-Time Haplotype Inference on Pedigrees Without Recombinations....Pages 56-67
Phylogenetic Network Inferences Through Efficient Haplotyping....Pages 68-79
Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems....Pages 80-91
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model....Pages 92-102
How Many Transcripts Does It Take to Reconstruct the Splice Graph?....Pages 103-114
Multiple Structure Alignment and Consensus Identification for Proteins....Pages 115-125
Procrastination Leads to Efficient Filtration for Local Multiple Alignment....Pages 126-137
Controlling Size When Aligning Multiple Genomic Sequences with Duplications....Pages 138-149
Reducing Distortion in Phylogenetic Networks....Pages 150-161
Imputing Supertrees and Supernetworks from Quartets....Pages 162-162
A Unifying View of Genome Rearrangements....Pages 163-173
Efficient Sampling of Transpositions and Inverted Transpositions for Bayesian MCMC....Pages 174-185
Alignment with Non-overlapping Inversions in O ( n 3 )-Time....Pages 186-196
Accelerating Motif Discovery: Motif Matching on Parallel Hardware....Pages 197-206
Segmenting Motifs in Protein-Protein Interface Surfaces....Pages 207-218
Protein Side-Chain Placement Through MAP Estimation and Problem-Size Reduction....Pages 219-230
On the Complexity of the Crossing Contact Map Pattern Matching Problem....Pages 231-241
A Fuzzy Dynamic Programming Approach to Predict RNA Secondary Structure....Pages 242-251
Landscape Analysis for Protein-Folding Simulation in the H-P Model....Pages 252-261
Rapid ab initio RNA Folding Including Pseudoknots Via Graph Tree Decomposition....Pages 262-273
Flux-Based vs. Topology-Based Similarity of Metabolic Genes....Pages 274-285
Combinatorial Methods for Disease Association Search and Susceptibility Prediction....Pages 286-297
Integer Linear Programs for Discovering Approximate Gene Clusters....Pages 298-309
Approximation Algorithms for Bi-clustering Problems....Pages 310-320
Improving the Layout of Oligonucleotide Microarrays: Pivot Partitioning....Pages 321-332
Accelerating the Computation of Elementary Modes Using Pattern Trees....Pages 333-343
A Linear-Time Algorithm for Studying Genetic Variation....Pages 344-354
New Constructive Heuristics for DNA Sequencing by Hybridization....Pages 355-365
Optimal Probing Patterns for Sequencing by Hybridization....Pages 366-375
Gapped Permutation Patterns for Comparative Genomics....Pages 376-387
Segmentation with an Isochore Distribution....Pages 388-399
Back Matter....Pages -
