Algorithms in Bioinformatics

Here are the refereed proceedings of the 6th International Workshop on Algorithms in Bioinformatics, WABI 2006, held in the course of the ALGO 2006 conference meetings. The book presents 36 revised full papers addressing all current issues of algorithms in bioinformatics, from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. For the first time, coverage extends to machine-learning approaches along with combinatorial optimization.

Inhalt

Measures of Codon Bias in Yeast, the tRNA Pairing Index and Possible DNA Repair Mechanisms.- Decomposing Metabolomic Isotope Patterns.- A Method to Design Standard HMMs with Desired Length Distribution for Biological Sequence Analysis.- Efficient Model-Based Clustering for LC-MS Data.- A Bayesian Algorithm for Reconstructing Two-Component Signaling Networks.- Linear-Time Haplotype Inference on Pedigrees Without Recombinations.- Phylogenetic Network Inferences Through Efficient Haplotyping.- Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems.- On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.- How Many Transcripts Does It Take to Reconstruct the Splice Graph?.- Multiple Structure Alignment and Consensus Identification for Proteins.- Procrastination Leads to Efficient Filtration for Local Multiple Alignment.- Controlling Size When Aligning Multiple Genomic Sequences with Duplications.- Reducing Distortion in Phylogenetic Networks.- Imputing Supertrees and Supernetworks from Quartets.- A Unifying View of Genome Rearrangements.- Efficient Sampling of Transpositions and Inverted Transpositions for Bayesian MCMC.- Alignment with Non-overlapping Inversions in O(n 3)-Time.- Accelerating Motif Discovery: Motif Matching on Parallel Hardware.- Segmenting Motifs in Protein-Protein Interface Surfaces.- Protein Side-Chain Placement Through MAP Estimation and Problem-Size Reduction.- On the Complexity of the Crossing Contact Map Pattern Matching Problem.- A Fuzzy Dynamic Programming Approach to Predict RNA Secondary Structure.- Landscape Analysis for Protein-Folding Simulation in the H-P Model.- Rapid ab initio RNA Folding Including Pseudoknots Via Graph Tree Decomposition.- Flux-Based vs. Topology-Based Similarity of Metabolic Genes.- Combinatorial Methods for Disease Association Search and Susceptibility Prediction.- Integer Linear Programs for Discovering Approximate Gene Clusters.- Approximation Algorithms for Bi-clustering Problems.- Improving the Layout of Oligonucleotide Microarrays: Pivot Partitioning.- Accelerating the Computation of Elementary Modes Using Pattern Trees.- A Linear-Time Algorithm for Studying Genetic Variation.- New Constructive Heuristics for DNA Sequencing by Hybridization.- Optimal Probing Patterns for Sequencing by Hybridization.- Gapped Permutation Patterns for Comparative Genomics.- Segmentation with an Isochore Distribution.