Algorithms in Bioinformatics: 4th International Workshop, WABI 2004, Bergen, Norway, September 17-21, 2004. Proceedings

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 -