This book constitutes the refereed proceedings of the 4th International Workshop on Algorithms in Bioinformatics, WABI 2004, held in Bergen, Norway, in September 2004.
The 39 revised full papers presented were carefully reviewed and selected from 117 submissions. Among the topics addressed are all current issues of algorithms in bioinformatics, such as exact and approximate algorithms for genomics, genetics, sequence analysis, gene and signal recognition, alignment, molecular evolution, phylogenetics, structure determination or prediction, gene expression and gene networks, proteomics, functional genomics, and drug design.
Author(s): Joel V. Earnest-DeYoung, Emmanuelle Lerat, Bernard M. E. Moret (auth.), Inge Jonassen, Junhyong Kim (eds.)
Series: Lecture Notes in Computer Science 3240 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004
Language: English
Pages: 477
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 -
Reversing Gene Erosion – Reconstructing Ancestral Bacterial Genomes from Gene-Content and Order Data....Pages 1-13
Reconstructing Ancestral Gene Orders Using Conserved Intervals....Pages 14-25
Sorting by Reversals with Common Intervals....Pages 26-37
A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns....Pages 38-49
A 1.5-Approximation Algorithm for Sorting by Transpositions and Transreversals....Pages 50-61
Algorithms for Finding Maximal-Scoring Segment Sets....Pages 62-73
Gapped Local Similarity Search with Provable Guarantees....Pages 74-86
Monotone Scoring of Patterns with Mismatches....Pages 87-98
Suboptimal Local Alignments Across Multiple Scoring Schemes....Pages 99-110
A Faster Reliable Algorithm to Estimate the p-Value of the Multinomial llr Statistic....Pages 111-122
Adding Hidden Nodes to Gene Networks....Pages 123-134
Joint Analysis of DNA Copy Numbers and Gene Expression Levels....Pages 135-146
Searching for Regulatory Elements of Alternative Splicing Events Using Phylogenetic Footprinting....Pages 147-158
Supervised Learning-Aided Optimization of Expert-Driven Functional Protein Sequence Annotation....Pages 159-169
Multiple Vector Seeds for Protein Alignment....Pages 170-181
Solving the Protein Threading Problem by Lagrangian Relaxation....Pages 182-193
Protein-Protein Interfaces: Recognition of Similar Spatial and Chemical Organizations....Pages 194-205
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences....Pages 206-217
Local Search Heuristic for Rigid Protein Docking....Pages 218-229
Sequence Database Compression for Peptide Identification from Tandem Mass Spectra....Pages 230-241
Linear Reduction for Haplotype Inference....Pages 242-253
A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis....Pages 254-265
Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction....Pages 266-277
Approximation Algorithms for the Selection of Robust Tag SNPs....Pages 278-289
The Minisatellite Transformation Problem Revisited: A Run Length Encoded Approach....Pages 290-301
A Faster and More Space-Efficient Algorithm for Inferring Arc-Annotations of RNA Sequences Through Alignment....Pages 302-313
New Algorithms for Multiple DNA Sequence Alignment....Pages 314-325
Chaining Algorithms for Alignment of Draft Sequence....Pages 326-337
Translation Initiation Sites Prediction with Mixture Gaussian Models....Pages 338-349
Online Consensus and Agreement of Phylogenetic Trees....Pages 350-361
Relation of Residues in the Variable Region of 16S rDNA Sequences and Their Relevance to Genus-Specificity....Pages 362-373
Topological Rearrangements and Local Search Method for Tandem Duplication Trees....Pages 374-387
Phylogenetic Super-networks from Partial Trees....Pages 388-399
Genome Identification and Classification by Short Oligo Arrays....Pages 400-411
Novel Tree Edit Operations for RNA Secondary Structure Comparison....Pages 412-425
The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics....Pages 426-437
Integrating Sample-Driven and Pattern-Driven Approaches in Motif Finding....Pages 438-449
Finding Optimal Pairs of Patterns....Pages 450-462
Finding Missing Patterns....Pages 463-474
Back Matter....Pages -
