Algorithms in Bioinformatics

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms in Bioinformatics, WABI 2007, held in Philadelphia, PA, USA in September 2007.

The 38 revised full papers presented together with the abstract of a keynote talk were carefully reviewed and selected from 133 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. Numerous biological problems are dealt with, including genetic mapping, sequence alignment and sequence analysis, phylogeny, comparative genomics, and protein structure. Furthermore the papers feature high-performance computing approaches to computationally hard learning and optimization problems in bioinformatics and cover methods, software and dataset repositories for development and testing of such algorithms and their underlying models.

Zusammenfassung

The refereed proceedings from the 7th International Workshop on Algorithms in Bioinformatics are provided in this volume. Papers address current issues in algorithms in bioinformatics, ranging from mathematical tools to experimental studies of approximation algorithms to significant computational analyses. Biological problems examined include genetic mapping, sequence alignment and analysis, phylogeny, comparative genomics, and protein structure.

Inhalt
Shotgun Protein Sequencing.- Locality Kernels for Protein Classification.- When Less Is More: Improving Classification of Protein Families with a Minimal Set of Global Features.- Fault Tolerance for Large Scale Protein 3D Reconstruction from Contact Maps.- Bringing Folding Pathways into Strand Pairing Prediction.- A Fast and Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage.- Two Birds, One Stone: Selecting Functionally Informative Tag SNPs for Disease Association Studies.- Genotype Error Detection Using Hidden Markov Models of Haplotype Diversity.- Haplotype Inference Via Hierarchical Genotype Parsing.- Seeded Tree Alignment and Planar Tanglegram Layout.- Inferring Models of Rearrangements, Recombinations, and Horizontal Transfers by the Minimum Evolution Criterion.- An ?(n 2/logn) Speed-Up of Heuristics for the Gene-Duplication Problem.- Incremental Discovery of Irredundant Motif Bases in Time O(|?|n 2 logn).- A Graph Clustering Approach to Weak Motif Recognition.- Informative Motifs in Protein Family Alignments.- Topology Independent Protein Structural Alignment.- Generalized Pattern Search and Mesh Adaptive Direct Search Algorithms for Protein Structure Prediction.- Alignment-Free Local Structural Search by Writhe Decomposition.- Defining and Computing Optimum RMSD for Gapped Multiple Structure Alignment.- Using Protein Domains to Improve the Accuracy of Ab Initio Gene Finding.- Genomic Signatures in De Bruijn Chains.- Fast Kernel Methods for SVM Sequence Classifiers.- On-Line Viterbi Algorithm for Analysis of Long Biological Sequences.- Predicting Protein Folding Kinetics Via Temporal Logic Model Checking.- Efficient Algorithms to Explore Conformation Spaces of Flexible ProteinLoops.- Algorithms for the Extraction of Synteny Blocks from Comparative Maps.- Computability of Models for Sequence Assembly.- Fast Algorithms for Selecting Specific siRNA in Complete mRNA Data.- RNA Folding Including Pseudoknots: A New Parameterized Algorithm and Improved Upper Bound.- HFold: RNA Pseudoknotted Secondary Structure Prediction Using Hierarchical Folding.- Homology Search with Fragmented Nucleic Acid Sequence Patterns.- Fast Computation of Good Multiple Spaced Seeds.- Inverse Sequence Alignment from Partial Examples.- Novel Approaches in Psychiatric Genomics.- The Point Placement Problem on a Line Improved Bounds for Pairwise Distance Queries.- Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach.- Efficient and Accurate Construction of Genetic Linkage Maps from Noisy and Missing Genotyping Data.- A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence.- Composing Globally Consistent Pathway Parameter Estimates Through Belief Propagation.