Algorithms in Bioinformatics: Second International Workshop, WABI 2002 Rome, Italy, September 17–21, 2002 Proceedings

L. R. Grate, C. Bhattacharyya, M. I. Jordan, I. S. Mian (auth.), Roderic Guigó, Dan Gusfield (eds.)3540442111, 9783540442110

We are pleased to present the proceedings of the Second Workshop on Al- rithms in Bioinformatics (WABI 2002), which took place on September 17-21, 2002 in Rome, Italy. The WABI workshop was part of a three-conference me- ing, which, in addition to WABI, included the ESA and APPROX 2002. The three conferences are jointly called ALGO 2002, and were hosted by the F- ulty of Engineering, University of Rome “La Sapienza”. Seehttp://www.dis. uniroma1.it/˜algo02 for more details. The Workshop on Algorithms in Bioinformatics covers research in all areas of algorithmic work in bioinformatics and computational biology. The emphasis is on discrete algorithms that address important problems in molecular biology, genomics,andgenetics,thatarefoundedonsoundmodels,thatarecomputati- ally e?cient, and that have been implemented and tested in simulations and on real datasets. The goal is to present recent research results, including signi?cant work in progress, and to identify and explore directions of future research. Original research papers (including signi?cant work in progress) or sta- of-the-art surveys were solicited on all aspects of algorithms in bioinformatics, including, but not limited to: 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.

---

Table of contents :
Simultaneous Relevant Feature Identification and Classification in High-Dimensional Spaces….Pages 1-9
Pooled Genomic Indexing (PGI): Mathematical Analysis and Experiment Design….Pages 10-28
Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem….Pages 29-43
Methods for Inferring Block-Wise Ancestral History from Haploid Sequences….Pages 44-59
Finding Signal Peptides in Human Protein Sequences Using Recurrent Neural Networks….Pages 60-67
Generating Peptide Candidates from Amino-Acid Sequence Databases for Protein Identification via Mass Spectrometry….Pages 68-81
Improved Approximation Algorithms for NMR Spectral Peak Assignment….Pages 82-96
Efficient Methods for Inferring Tandem Duplication History….Pages 97-111
Genome Rearrangement Phylogeny Using Weighbor….Pages 112-125
Segment Match Refinement and Applications….Pages 126-139
Extracting Common Motifs under the Levenshtein Measure: Theory and Experimentation….Pages 140-156
Fast Algorithms for Finding Maximum-Density Segments of a Sequence with Applications to Bioinformatics….Pages 157-171
FAUST: An Algorithm for Extracting Functionally Relevant Templates from Protein Structures….Pages 172-184
Efficient Unbound Docking of Rigid Molecules….Pages 185-200
A Method of Consolidating and Combining EST and mRNA Alignments to a Genome to Enumerate Supported Splice Variants….Pages 201-209
A Method to Improve the Performance of Translation Start Site Detection and Its Application for Gene Finding….Pages 210-219
Comparative Methods for Gene Structure Prediction in Homologous Sequences….Pages 220-234
MultiProt — A Multiple Protein Structural Alignment Algorithm….Pages 235-250
A Hybrid Scoring Function for Protein Multiple Alignment….Pages 251-262
Functional Consequences in Metabolic Pathways from Phylogenetic Profiles….Pages 263-276
Finding Founder Sequences from a Set of Recombinants….Pages 277-286
Estimating the Deviation from a Molecular Clock….Pages 287-299
Exploring the Set of All Minimal Sequences of Reversals — An Application to Test the Replication-Directed Reversal Hypothesis….Pages 300-315
Approximating the Expected Number of Inversions Given the Number of Breakpoints….Pages 316-330
Invited Lecture — Accelerating Smith-Waterman Searches….Pages 331-342
Sequence-Length Requirements for Phylogenetic Methods….Pages 343-356
Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle….Pages 357-374
NeighborNet: An Agglomerative Method for the Construction of Planar Phylogenetic Networks….Pages 375-391
On the Control of Hybridization Noise in DNA Sequencing-by-Hybridization….Pages 392-403
Restricting SBH Ambiguity via Restriction Enzymes….Pages 404-417
Invited Lecture — Molecule as Computation: Towards an Abstraction of Biomolecular Systems….Pages 418-418
Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search….Pages 419-433
Rapid Large-Scale Oligonucleotide Selection for Microarrays….Pages 434-434
Border Length Minimization in DNA Array Design * ….Pages 435-448
The Enhanced Suffix Array and Its Applications to Genome Analysis….Pages 449-463
The Algorithmic of Gene Teams….Pages 464-476
Combinatorial Use of Short Probes for Differential Gene Expression Profiling….Pages 477-490
Designing Specific Oligonucleotide Probes for the Entire S. cerevisiae Transcriptome….Pages 491-505
K -ary Clustering with Optimal Leaf Ordering for Gene Expression Data….Pages 506-520
Inversion Medians Outperform Breakpoint Medians in Phylogeny Reconstruction from Gene-Order Data….Pages 521-536
Modified Mincut Supertrees….Pages 537-551