Computer Science
Department

Technion – Israel Institute of Technology

Length-sensitive Algorithms

for Sorting by Reversals:

a Phylogeny-based Evaluation

Ron
Y. Pinter

October 23, 2003

**Outline**

**Genome Rearrangement**

**Sorting by Reversals**

**Example**

**Our Model**

**Cost Functions**

**Family of Cost Functions**

**Problems**

**Extremal Costs**

**Our Algorithmic Workhorses**

**MedianEject(a,b)**

**Sample Run**

**ReversalSort(a,b)**

**Algorithmic Improvements**

**Dynamic Programming Scheme**

**Summary of Results: Bounds**

on Costs and Approximation Ratios

**Evaluation Framework**

**Issues**

**Data Sets**

**Number of Common Genes**

**Genome Subsets**

**Early “Validation”**

**Reconstruction**

**Tree Similarity Measures**

**Approximation etc.**

**Finding a**

**Finding a with puzzling**

**RF(T**_{a},T_{ref})
for Matrin et al.

**Prediction***

**Open Problems: Algorithmic**

**Open Problems: Modeling**

**Future Work**

**Acknowledgements**