# On the Inversion-Indel Distance

Willing E, Zaccaria S, Braga MDV, Stoye J (2013)

BMC Bioinformatics 14(Suppl 15: Proc. of RECOMB-CG 2013).

Download

*Journal Article*|

*Published*|

*English*

Author

Department

Abstract

Background
The inversion distance, that is the distance between two unichromosomal genomes with the same content allowing only inversions of DNA segments, can be computed thanks to a pioneering approach of Hannenhalli and Pevzner in 1995. In 2000, El-Mabrouk extended the inversion model to allow the comparison of unichromosomal genomes with unequal contents, thus insertions and deletions of DNA segments besides inversions. However, an exact algorithm was presented only for the case in which we have insertions alone and no deletion (or vice versa), while a heuristic was provided for the symmetric case, that allows both insertions and deletions and is called the inversion-indel distance. In 2005, Yancopoulos, Attie and Friedberg started a new branch of research by introducing the generic double cut and join (DCJ) operation, that can represent several genome rearrangements (including inversions). Among others, the DCJ model gave rise to two important results. First, it has been shown that the inversion distance can be computed in a simpler way with the help of the DCJ operation. Second, the DCJ operation originated the DCJ-indel distance, that allows the comparison of genomes with unequal contents, considering DCJ, insertions and deletions, and can be computed in linear time.
Results
In the present work we put these two results together to solve an open problem, showing that, when the graph that represents the relation between the two compared genomes has no bad components, the inversion-indel distance is equal to the DCJ-indel distance. We also give a lower and an upper bound for the inversion-indel distance in the presence of bad components.

Publishing Year

ISSN

PUB-ID

### Cite this

Willing E, Zaccaria S, Braga MDV, Stoye J. On the Inversion-Indel Distance.

*BMC Bioinformatics*. 2013;14(Suppl 15: Proc. of RECOMB-CG 2013).Willing, E., Zaccaria, S., Braga, M. D. V., & Stoye, J. (2013). On the Inversion-Indel Distance.

*BMC Bioinformatics*,*14*(Suppl 15: Proc. of RECOMB-CG 2013).Willing, E., Zaccaria, S., Braga, M. D. V., and Stoye, J. (2013). On the Inversion-Indel Distance.

*BMC Bioinformatics*14.Willing, E., et al., 2013. On the Inversion-Indel Distance.

*BMC Bioinformatics*, 14(Suppl 15: Proc. of RECOMB-CG 2013).E. Willing, et al., “On the Inversion-Indel Distance”,

*BMC Bioinformatics*, vol. 14, 2013.Willing, E., Zaccaria, S., Braga, M.D.V., Stoye, J.: On the Inversion-Indel Distance. BMC Bioinformatics. 14, (2013).

Willing, Eyla, Zaccaria, Simone, Braga, Marília D. V., and Stoye, Jens. “On the Inversion-Indel Distance”.

*BMC Bioinformatics*14.Suppl 15: Proc. of RECOMB-CG 2013 (2013).**Main File(s)**

File Name

Access Level

Open Access

Last Uploaded

2013-10-23 10:17:08

This data publication is cited in the following publications:

This publication cites the following data publications:

### 1 Citation in Europe PMC

Data provided by Europe PubMed Central.

Recombination-aware alignment of diploid individuals.

Makinen V, Valenzuela D.,

PMID: 25572943

Makinen V, Valenzuela D.,

*BMC Genomics*15 Suppl 6(), 2014PMID: 25572943

### 19 References

Data provided by Europe PubMed Central.

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals

AUTHOR UNKNOWN, 1999

AUTHOR UNKNOWN, 1999

Identifying functional decline: a methodological challenge.

Grimmer K, Beaton K, Hendry K.,

PMID: 24009434

Grimmer K, Beaton K, Hendry K.,

*Patient Relat Outcome Meas*4(), 2013PMID: 24009434

Sorting signed permutations by reversals and insertions/deletions of contiguous segments

AUTHOR UNKNOWN, 2001

AUTHOR UNKNOWN, 2001

Efficient sorting of genomic permutations by translocation, inversion and block interchange.

Yancopoulos S, Attie O, Friedberg R.,

PMID: 15951307

Yancopoulos S, Attie O, Friedberg R.,

*Bioinformatics*21(16), 2005PMID: 15951307

AUTHOR UNKNOWN, 2006

A new linear time algorithm to compute the genomic distance via the double cut and join distance

AUTHOR UNKNOWN, 2009

AUTHOR UNKNOWN, 2009

DCJ path formulation for genome transformations which include insertions, deletions, and duplications.

Yancopoulos S, Friedberg R.,

PMID: 19803734

Yancopoulos S, Friedberg R.,

*J. Comput. Biol.*16(10), 2009PMID: 19803734

Double cut and join with insertions and deletions.

Braga MD, Willing E, Stoye J.,

PMID: 21899423

Braga MD, Willing E, Stoye J.,

*J. Comput. Biol.*18(9), 2011PMID: 21899423

DCJ-indel and DCJ-substitution distances with distinct operation costs.

da Silva PH, Machado R, Dantas S, Braga MD.,

PMID: 23879938

da Silva PH, Machado R, Dantas S, Braga MD.,

*Algorithms Mol Biol*8(1), 2013PMID: 23879938

An overview of genomic distances modeled with indels

AUTHOR UNKNOWN, 2013

AUTHOR UNKNOWN, 2013

Introduction to Computational Molecular Biology

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 0

Genome rearrangement by the double cut and join operation.

Friedberg R, Darling AE, Yancopoulos S.,

PMID: 18566774

Friedberg R, Darling AE, Yancopoulos S.,

*Methods Mol. Biol.*452(), 2008PMID: 18566774

Genome rearrangements and sorting by reversals

AUTHOR UNKNOWN, 1993

AUTHOR UNKNOWN, 1993

The solution space of sorting by DCJ.

Braga MD, Stoye J.,

PMID: 20874401

Braga MD, Stoye J.,

*J. Comput. Biol.*17(9), 2010PMID: 20874401

Transforming Men Into Mice (Polynomial Algorithm for Genomic Distance Problem)

AUTHOR UNKNOWN, 1995

AUTHOR UNKNOWN, 1995

The Inversion Distance Problem

AUTHOR UNKNOWN, 2005

AUTHOR UNKNOWN, 2005

Restricted DCJ-indel model: sorting linear genomes with DCJ and indels.

da Silva PH, Machado R, Dantas S, Braga MD.,

PMID: 23281630

da Silva PH, Machado R, Dantas S, Braga MD.,

*BMC Bioinformatics*13 Suppl 19(), 2012PMID: 23281630

DCJ-Indel sorting revisited

AUTHOR UNKNOWN, 2013

AUTHOR UNKNOWN, 2013

Restricted DCJ model: rearrangement problems with chromosome reincorporation.

Kovac J, Warren R, Braga MD, Stoye J.,

PMID: 21899428

Kovac J, Warren R, Braga MD, Stoye J.,

*J. Comput. Biol.*18(9), 2011PMID: 21899428

### Export

0 Marked Publications### Web of Science

View record in Web of Science®### Sources

PMID: 24564182

PubMed | Europe PMC