Algorithms in Bioinformatics

1. Front Matter

   PDF

2. Minimum Factorization Agreement of Spliced ESTs

   • Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola, Raffaella Rizzi

   Pages 1-12

3. Annotating Fragmentation Patterns

   • Sebastian Böcker, Florian Rasche, Tamara Steijger

   Pages 13-24

4. biRNA: Fast RNA-RNA Binding Sites Prediction

   • Hamidreza Chitsaz, Rolf Backofen, S. Cenk Sahinalp

   Pages 25-36

5. Quantifying Systemic Evolutionary Changes by Color Coding Confidence-Scored PPI Networks

   • Phuong Dao, Alexander Schönhuth, Fereydoun Hormozdiari, Iman Hajirasouliha, S. Cenk Sahinalp, Martin Ester

   Pages 37-48

6. PMFastR: A New Approach to Multiple RNA Structure Alignment

   • Daniel DeBlasio, Jocelyne Bruand, Shaojie Zhang

   Pages 49-61

7. On the Upper Bound of the Prediction Accuracy of Residue Contacts in Proteins with Correlated Mutations: The Case Study of the Similarity Matrices

   • Pietro Di Lena, Piero Fariselli, Luciano Margara, Marco Vassura, Rita Casadio

   Pages 62-72

8. Constructing Majority-Rule Supertrees

   • Jianrong Dong, David Fernández-Baca, F. R. McMorris

   Pages 73-84

9. SCJ: A Variant of Breakpoint Distance for Which Sorting, Genome Median and Genome Halving Problems Are Easy

   • Pedro Feijão, João Meidanis

   Pages 85-96

10. A Simple, Practical and Complete \(O(\frac{n^3}{ \log n})\)-Time Algorithm for RNA Folding Using the Four-Russians Speedup

    • Yelena Frid, Dan Gusfield

    Pages 97-107

11. Back-Translation for Discovering Distant Protein Homologies

    • Marta Gîrdea, Laurent Noé, Gregory Kucherov

    Pages 108-120

12. A Markov Classification Model for Metabolic Pathways

    • Timothy Hancock, Hiroshi Mamitsuka

    Pages 121-132

13. Mimosa: Mixture Model of Co-expression to Detect Modulators of Regulatory Interaction

    • Matthew Hansen, Logan Everett, Larry Singh, Sridhar Hannenhalli

    Pages 133-144

14. Phylogenetic Comparative Assembly

    • Peter Husemann, Jens Stoye

    Pages 145-156

15. K-Partite RNA Secondary Structures

    • Minghui Jiang, Pedro J. Tejada, Ramoni O. Lasisi, Shanhong Cheng, D. Scott Fechser

    Pages 157-168

16. Efficient Algorithms for Analyzing Segmental Duplications, Deletions, and Inversions in Genomes

    • Crystal L. Kahn, Shay Mozes, Benjamin J. Raphael

    Pages 169-180

17. Predicting Gene Structures from Multiple RT-PCR Tests

    • Jakub Kováč, Tomáš Vinař, Broňa Brejová

    Pages 181-193

18. A Tree Based Method for the Rapid Screening of Chemical Fingerprints

    • Thomas G. Kristensen, Jesper Nielsen, Christian N. S. Pedersen

    Pages 194-205

19. Generalizing the Four Gamete Condition and Splits Equivalence Theorem: Perfect Phylogeny on Three State Characters

    • Fumei Lam, Dan Gusfield, Srinath Sridhar

    Pages 206-219

20. Decoding Synteny Blocks and Large-Scale Duplications in Mammalian and Plant Genomes

    • Qian Peng, Max A. Alekseyev, Glenn Tesler, Pavel A. Pevzner

    Pages 220-232

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.

• RNA
• algorithms
• bioinformatics
• clustering
• computational biology
• data analysis
• data mining
• genetic mapping
• genome
• genome analysis
• genomic indexing
• phylogenetic diversity
• protein analysis
• protein classification
• sequence analysis
• algorithm analysis and problem complexity

• Center for Bioinformatics and Computational Biology, and Department of Computer Science, University of Maryland, College Park, USA

  Steven L. Salzberg

• Department of Computer Sciences, The University of Texas at Austin, USA

  Tandy Warnow

Policies and ethics