Sorting by Block-Interchanges and Signed Reversals

A block-interchange is a rearrangement event that exchanges two, not necessarily consecutive, contiguous regions in a genome, maintaining the original orientation. Signed reversals are events that invert and change the orientation of a region in a genome. Both events are important for the comparativ...

Full description

Saved in:
Bibliographic Details
Main Authors: Mira, C., Meidanis, J.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Bioinformatics
Biological cells
Data structures
Extraterrestrial measurements
Frequency
Genomics
Polynomials
Sorting
Time measurement
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A block-interchange is a rearrangement event that exchanges two, not necessarily consecutive, contiguous regions in a genome, maintaining the original orientation. Signed reversals are events that invert and change the orientation of a region in a genome. Both events are important for the comparative analysis of genomes. For this reason, we propose a new measure that consists in finding a minimum sequence of block-interchanges and signed reversals that transforms a genome into another. For each event, we assign a weight related to its norm and we argue the adequacy of this parameter to indicate the power of each event. We present a formula for the rearrangement measure and a polynomial time sorting algorithm for finding a sequence of block-interchanges and signed reversals that transforms a unichromosomal genome into another
DOI:10.1109/ITNG.2007.184