Skip to content

Combinatorics of Genome Rearrangements

ISBN-10: 0262062828

ISBN-13: 9780262062824

Edition: 2009

Authors: Guillaume Fertin, Anthony E. Labarre, Irena Rusu, Eric Tannier, St�phane Vialette

List price: $45.00
Blue ribbon 30 day, 100% satisfaction guarantee!
Buy eBooks
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Customers also bought

Book details

List price: $45.00
Copyright year: 2009
Publisher: MIT Press
Publication date: 6/5/2009
Binding: Hardcover
Pages: 312
Size: 7.25" wide x 9.50" long x 1.00" tall
Weight: 1.342
Language: English

Guillaume Fertin is Professor of Computer Science at the University of Nantes.

Irena Rusu is Professor of Computer Science at the University of Nantes.

Stephane Vialette is a Researcher in the Gaspard-Monge Institute of Electronics and Computer Science at the University of Paris-Est Marne-la-Vallee.

A Minimalist Introduction to Molecular Evolution
Birth of the Combinatorics of Genome Rearrangements
Statement of the Problem
Scope of This Survey
Overview of the Models
Organization of the Book
Duplication-Free Models: Permutations
Genomes as Permutations
The Symmetric Group
The Cycles of a Permutation
Signed Permutations
Distances on Permutation Groups
Circular Permutations
First Measures of Similarity between Permutations
Distances between Unsigned Permutations
Transposition Distance
Prefix Transposition Distance
Reversal Distance
Prefix Reversal Distance (Pancake-Flipping)
Relations between Distances on Unsigned Permutations
Distances between Signed Permutations
Conserved Interval Distance
Signed Reversal Distance
Variants of Sorting by Reversals
Combined Operations
Double Cut-and-Joins
Rearrangements of Partial Orders
Genomes as Partially Ordered Sets
Partially Ordered Sets
Constructing a Poset
Reversal Distance
Breakpoint Distance
Graph-Theoretic and Linear Algebra Formulations
Simple Permutations and the Interleaving Graph
The Overlap Graph
The Local Complementation of a Graph
The Matrix Tightness Problem
Extension to Sorting by Transpositions
The Intermediate Case of Directed Local Complementation
Models Handling Duplications: Strings
Biological Motivations
Strings and Rearrangements on Strings
Balanced Strings
How to Deal with Multiple Copies?
Distances between Arbitrary Strings
The Match-and-Prune Model
The Block Edit Model
Distances between Balanced Strings
Minimum Common String Partition Problems
Reversal Distance
Unsigned Transpositions
Unsigned Block Interchanges
Relations between Distances
Multichromosomal Models
Paths and Cycles
Translocation Distance
Double Cut-and-Joins (2-Break Rearrangement)
k-Break Rearrangement
Fusions, Fissions, Translocations, and Reversals
Rearrangements with Partially Ordered Chromosomes
Cycles of a Permutation
A Model for Multichromosomal Circular Genomes
A Generalization to Signed Genomes
Set Systems and the Syntenic Distance
Structural Properties
Lower Bounds
Algorithmic Results
Conjectures and Open Problems
Multigenomic Models
Median and Halving Problems
Breakpoint Median
Reversal and DCJ Median
Duplicated Genomes
Other Variants, Generalizations, and Discussion
Rearrangement Phylogenies
The Large Parsimony Problem
The Large Parsimony Problem with Gene Orders
Heuristics for the Breakpoint/Reversal Phylogeny Problem
Pairwise Rearrangements
Phylogeny Reconstruction and Medians
Open Problems
Complexity Issues
Tightness of Bounds
Graph Theory
Undirected Graphs
Directed Graphs
Complexity Theory
The Class NP
Some NP-Complete Problems