These proceedings contain papers from the 2009 Workshop on Algorithms in Bioinformatics (WABI), held at the University of Pennsylvania in Philadelphia, Pennsylvania during September 12-13, 2009. WABI 2009 was the ninth annual conference in this series, which focuses on novel algorithms that address imp- tantproblemsingenomics,molecularbiology,andevolution.Theconference- phasizes research that describes computationally e?cient algorithms and data structures that have been implemented and tested in simulations and on real data. WABI is sponsored by the European Association for Theoretical C- puter Science (EATCS) and the International Society for Computational Bi- ogy (ISCB). WABI 2009 was supported by the Penn Genome Frontiers Institute and the Penn Center for Bioinformatics at the University of Pennsylvania. For the 2009 conference, 90 full papers were submitted for review by the Program Committee, and from this strong ?eld of submissions, 34 papers were chosen for presentation at the conference and publication in the proceedings. The ?nal programcovered a wide range of topics including gene interaction n- works, molecular phylogeny, RNA and protein structure, and genome evolution.

Minimum Factorization Agreement of Spliced ESTs.- Annotating Fragmentation Patterns.- biRNA: Fast RNA-RNA Binding Sites Prediction.- Quantifying Systemic Evolutionary Changes by Color Coding Confidence-Scored PPI Networks.- PMFastR: A New Approach to Multiple RNA Structure Alignment.- On the Upper Bound of the Prediction Accuracy of Residue Contacts in Proteins with Correlated Mutations: The Case Study of the Similarity Matrices.- Constructing Majority-Rule Supertrees.- SCJ: A Variant of Breakpoint Distance for Which Sorting, Genome Median and Genome Halving Problems Are Easy.- A Simple, Practical and Complete -Time Algorithm for RNA Folding Using the Four-Russians Speedup.- Back-Translation for Discovering Distant Protein Homologies.- A Markov Classification Model for Metabolic Pathways.- Mimosa: Mixture Model of Co-expression to Detect Modulators of Regulatory Interaction.- Phylogenetic Comparative Assembly.- K-Partite RNA Secondary Structures.- Efficient Algorithms for Analyzing Segmental Duplications, Deletions, and Inversions in Genomes.- Predicting Gene Structures from Multiple RT-PCR Tests.- A Tree Based Method for the Rapid Screening of Chemical Fingerprints.- Generalizing the Four Gamete Condition and Splits Equivalence Theorem: Perfect Phylogeny on Three State Characters.- Decoding Synteny Blocks and Large-Scale Duplications in Mammalian and Plant Genomes.- A General Framework for Local Pairwise Alignment Statistics with Gaps.- mpscan: Fast Localisation of Multiple Reads in Genomes.- Fast Prediction of RNA-RNA Interaction.- FlexSnap: Flexible Non-sequential Protein Structure Alignment.- A Non-parametric Bayesian Approach for Predicting RNA Secondary Structures.- Exact Score Distribution Computation for Similarity Searches in Ontologies.- Linear-Time Protein 3-D Structure Searching with Insertions and Deletions.- Visualizing Phylogenetic Treespace Using Cartographic Projections.- A Simulation Study Comparing Supertree and Combined Analysis Methods Using SMIDGen.- Aligning Biomolecular Networks Using Modular Graph Kernels.- MADMX: A Novel Strategy for Maximal Dense Motif Extraction.- Large-Scale Neighbor-Joining with NINJA.- A Unifying View on Approximation and FPT of Agreement Forests.- Structural Alignment of RNA with Complex Pseudoknot Structure.- Improving Inference of Transcriptional Regulatory Networks Based on Network Evolutionary Models.