Algorithms in Bioinformatics

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.

Includes supplementary material: sn.pub/extras

Inhalt
Simultaneous Relevant Feature Identification and Classification in High-Dimensional Spaces.- Pooled Genomic Indexing (PGI): Mathematical Analysis and Experiment Design.- Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem.- Methods for Inferring Block-Wise Ancestral History from Haploid Sequences.- Finding Signal Peptides in Human Protein Sequences Using Recurrent Neural Networks.- Generating Peptide Candidates from Amino-Acid Sequence Databases for Protein Identification via Mass Spectrometry.- Improved Approximation Algorithms for NMR Spectral Peak Assignment.- Efficient Methods for Inferring Tandem Duplication History.- Genome Rearrangement Phylogeny Using Weighbor.- Segment Match Refinement and Applications.- Extracting Common Motifs under the Levenshtein Measure: Theory and Experimentation.- Fast Algorithms for Finding Maximum-Density Segments of a Sequence with Applications to Bioinformatics.- FAUST: An Algorithm for Extracting Functionally Relevant Templates from Protein Structures.- Efficient Unbound Docking of Rigid Molecules.- A Method of Consolidating and Combining EST and mRNA Alignments to a Genome to Enumerate Supported Splice Variants.- A Method to Improve the Performance of Translation Start Site Detection and Its Application for Gene Finding.- Comparative Methods for Gene Structure Prediction in Homologous Sequences.- MultiProt A Multiple Protein Structural Alignment Algorithm.- A Hybrid Scoring Function for Protein Multiple Alignment.- Functional Consequences in Metabolic Pathways from Phylogenetic Profiles.- Finding Founder Sequences from a Set of Recombinants.- Estimating the Deviation from a Molecular Clock.- Exploring the Set of All Minimal Sequences of Reversals An Application to Test theReplication-Directed Reversal Hypothesis.- Approximating the Expected Number of Inversions Given the Number of Breakpoints.- Invited Lecture Accelerating Smith-Waterman Searches.- Sequence-Length Requirements for Phylogenetic Methods.- Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle.- NeighborNet: An Agglomerative Method for the Construction of Planar Phylogenetic Networks.- On the Control of Hybridization Noise in DNA Sequencing-by-Hybridization.- Restricting SBH Ambiguity via Restriction Enzymes.- Invited Lecture Molecule as Computation: Towards an Abstraction of Biomolecular Systems.- Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search.- Rapid Large-Scale Oligonucleotide Selection for Microarrays.- Border Length Minimization in DNA Array Design*.- The Enhanced Suffix Array and Its Applications to Genome Analysis.- The Algorithmic of Gene Teams.- Combinatorial Use of Short Probes for Differential Gene Expression Profiling.- Designing Specific Oligonucleotide Probes for the Entire S. cerevisiae Transcriptome.- K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data.- Inversion Medians Outperform Breakpoint Medians in Phylogeny Reconstruction from Gene-Order Data.- Modified Mincut Supertrees.