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.