Algorithms in Bioinformatics

Inge Jonassen Junhyong Kim (Eds.)

Table of Contents
Papers
Reversing Gene Erosion – Reconstructing Ancestral Bacterial Genomes
from Gene-Content and Order Data
Joel V. Earnest-De Young, Emmanuelle Lerat,
and Bernard M.E. Moret
1
Reconstructing Ancestral Gene Orders Using Conserved Intervals
Anne Bergeron, Mathieu Blanchette, Annie Chateau,
and Cedric Chauve
14
Sorting by Reversals with Common Intervals
Martin Figeac and Jean-Stéphane Varré
26
A Polynomial-Time Algorithm for the Matching
of Crossing Contact-Map Patterns
Jens Gramm
38
A 1.5-Approximation Algorithm for Sorting by Transpositions
and Transreversals
Tzvika Hartman and Roded Sharan
50
Algorithms for Finding Maximal-Scoring Segment Sets 62
Gapped Local Similarity Search with Provable Guarantees
Manikandan Narayanan and Richard M. Karp
74
Monotone Scoring of Patterns with Mismatches
Alberto Apostolico and Cinzia Pizzi
87
Suboptimal Local Alignments Across Multiple Scoring Schemes
Morris Michael, Christoph Dieterich, and Jens Stoye
99
A Faster Reliable Algorithm to Estimate the p-Value
of the Multinomial llr Statistic
Uri Keich and Niranjan Nagarajan
111
Adding Hidden Nodes to Gene Networks
Benny Chor and Tamir Tuller
123
Joint Analysis of DNA Copy Numbers and Gene Expression Levels
Doron Lipson, Amir Ben-Dor, Elinor Dehan, and Zohar Yakhini
135
Searching for Regulatory Elements of Alternative Splicing Events
Using Phylogenetic Footprinting
Daichi Shigemizu and Osamu Maruyama
147
Supervised Learning-Aided Optimization
of Expert-Driven Functional Protein Sequence Annotation
Lev Soinov, Alexander Kanapin, and Misha Kapushesky
159
Multiple Vector Seeds for Protein Alignment
Daniel G. Brown
170
Solving the Protein Threading Problem by Lagrangian Relaxation
Stefan Balev
182
Protein-Protein Interfaces:
Recognition of Similar Spatial and Chemical Organizations
Alexandra Shulman-Peleg, Shira Mintz, Ruth Nussinov,
and Haim J. Wolfson
194
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences
Stanislav Angelov, Sanjeev Khanna, Li Li, and Fernando Pereira
206
Local Search Heuristic for Rigid Protein Docking
Vicky Choi, Pankaj K. Agarwal, Herbert Edelsbrunner,
and Johannes Rudolph
218
Sequence Database Compression for Peptide Identification
from Tandem Mass Spectra
Nathan Edwards and Ross Lippert
230
Linear Reduction for Haplotype Inference
Jingwu He and Alex Zelikovsky
242
A New Integer Programming Formulation for the Pure Parsimony Problem
in Haplotype Analysis
Daniel G. Brown and Ian M. Harrower
254
Fast Hare: A Fast Heuristic
for Single Individual SNP Haplotype Reconstruction
Alessandro Panconesi and Mauro Sozio
266
Approximation Algorithms for the Selection of Robust Tag SNPs
Yao-Ting Huang, Kui Zhang, Ting Chen, and Kun-Mao Chao
278
The Minisatellite Transformation Problem Revisited:
A Run Length Encoded Approach
Behshad Behzadi and Jean-Marc Steyaert
290
A Faster and More Space-Efficient Algorithm
for Inferring Arc-Annotations of RNA Sequences Through Alignment
Jesper Jansson, See-Kiong Ng, Wing-Kin Sung, and Hugo Willy
302
New Algorithms for Multiple DNA Sequence Alignment
Daniel G. Brown and Alexander K. Hudek
314
Chaining Algorithms for Alignment of Draft Sequence
Mukund Sundararajan, Michael Brudno, Kerrin Small, Arend Sidow,
and Serafim Batzoglou
326
Translation Initiation Sites Prediction with Mixture Gaussian Models
Guoliang Li, Tze- Yun Leong, and Louxin Zhang
338
Online Consensus and Agreement of Phylogenetic Trees
Tanya Y. Berger-Wolf
350
Relation of Residues in the Variable Region of 16S rDNA Sequences
and Their Relevance to Genus-Specificity
Hemant J. Purohit, and Dhananjay V. Raje
362
Topological Rearrangements and Local Search Method
for Tandem Duplication Trees
Denis Bertrand and Olivier Gascuel
374
Phylogenetic Super-networks from Partial Trees
Daniel H. Huson, Tobias Dezulian, Tobias Klöpper, and Mike A. Steel
388
Genome Identification and Classification by Short Oligo Arrays
Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna,
Junhyong Kim, and Li-San Wang
400
Novel Tree Edit Operations for RNA Secondary Structure Comparison
Julien Allali and Marie-France Sagot
412
The Most Probable Labeling Problem in HMMs
and Its Application to Bioinformatics
Daniel G. Brown, and
426
Integrating Sample-Driven and Pattern-Driven Approaches
in Motif Finding
Sing-Hoi Sze, Songjian Lu, and Jianer Chen
438
Finding Optimal Pairs of Patterns
Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda,
Kenta Nakai, and Satoru Miyano
450
Finding Missing Patterns
Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen
463
Author Index 475

Another Bioinformatics Books
Download