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.
Author(s): Pavel A. Pevzner (auth.), Raffaele Giancarlo, Sridhar Hannenhalli (eds.)
Series: Lecture Notes in Computer Science 4645 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 434
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Structures; Discrete Mathematics in Computer Science; Probability and Statistics in Computer Science; Computational Biology/Bioinformatics
Front Matter....Pages -
Shotgun Protein Sequencing....Pages 1-1
Locality Kernels for Protein Classification....Pages 2-11
When Less Is More: Improving Classification of Protein Families with a Minimal Set of Global Features....Pages 12-24
Fault Tolerance for Large Scale Protein 3D Reconstruction from Contact Maps....Pages 25-37
Bringing Folding Pathways into Strand Pairing Prediction....Pages 38-48
A Fast and Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage....Pages 49-60
Two Birds, One Stone: Selecting Functionally Informative Tag SNPs for Disease Association Studies....Pages 61-72
Genotype Error Detection Using Hidden Markov Models of Haplotype Diversity....Pages 73-84
Haplotype Inference Via Hierarchical Genotype Parsing....Pages 85-97
Seeded Tree Alignment and Planar Tanglegram Layout....Pages 98-110
Inferring Models of Rearrangements, Recombinations, and Horizontal Transfers by the Minimum Evolution Criterion....Pages 111-123
An Ω ( n 2 /log n ) Speed-Up of Heuristics for the Gene-Duplication Problem....Pages 124-135
Incremental Discovery of Irredundant Motif Bases in Time O (| Σ | n 2 log n )....Pages 136-148
A Graph Clustering Approach to Weak Motif Recognition....Pages 149-160
Informative Motifs in Protein Family Alignments....Pages 161-170
Topology Independent Protein Structural Alignment....Pages 171-182
Generalized Pattern Search and Mesh Adaptive Direct Search Algorithms for Protein Structure Prediction....Pages 183-193
Alignment-Free Local Structural Search by Writhe Decomposition....Pages 194-195
Defining and Computing Optimum RMSD for Gapped Multiple Structure Alignment....Pages 196-207
Using Protein Domains to Improve the Accuracy of Ab Initio Gene Finding....Pages 208-215
Genomic Signatures in De Bruijn Chains....Pages 216-227
Fast Kernel Methods for SVM Sequence Classifiers....Pages 228-239
On-Line Viterbi Algorithm for Analysis of Long Biological Sequences....Pages 240-251
Predicting Protein Folding Kinetics Via Temporal Logic Model Checking....Pages 252-264
Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops....Pages 265-276
Algorithms for the Extraction of Synteny Blocks from Comparative Maps....Pages 277-288
Computability of Models for Sequence Assembly....Pages 289-301
Fast Algorithms for Selecting Specific siRNA in Complete mRNA Data....Pages 302-309
RNA Folding Including Pseudoknots: A New Parameterized Algorithm and Improved Upper Bound....Pages 310-322
HFold: RNA Pseudoknotted Secondary Structure Prediction Using Hierarchical Folding....Pages 323-334
Homology Search with Fragmented Nucleic Acid Sequence Patterns....Pages 335-345
Fast Computation of Good Multiple Spaced Seeds....Pages 346-358
Inverse Sequence Alignment from Partial Examples....Pages 359-370
Novel Approaches in Psychiatric Genomics....Pages 371-371
The Point Placement Problem on a Line – Improved Bounds for Pairwise Distance Queries....Pages 372-382
Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach....Pages 383-394
Efficient and Accurate Construction of Genetic Linkage Maps from Noisy and Missing Genotyping Data....Pages 395-406
A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence....Pages 407-419
Composing Globally Consistent Pathway Parameter Estimates Through Belief Propagation....Pages 420-430
Back Matter....Pages -
