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