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
OA
Journal Article | Published | English
Author
; ; ;
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)
Access Level
OA 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., BMC Genomics 15 Suppl 6(), 2014
PMID: 25572943

19 References

Data provided by Europe PubMed Central.

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals
AUTHOR UNKNOWN, 1999
Identifying functional decline: a methodological challenge.
Grimmer K, Beaton K, Hendry K., Patient Relat Outcome Meas 4(), 2013
PMID: 24009434
Sorting signed permutations by reversals and insertions/deletions of contiguous segments
AUTHOR UNKNOWN, 2001
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307

AUTHOR UNKNOWN, 2006
A new linear time algorithm to compute the genomic distance via the double cut and join distance
AUTHOR UNKNOWN, 2009
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
DCJ-indel and DCJ-substitution distances with distinct operation costs.
da Silva PH, Machado R, Dantas S, Braga MD., Algorithms Mol Biol 8(1), 2013
PMID: 23879938
An overview of genomic distances modeled with indels
AUTHOR UNKNOWN, 2013
Introduction to Computational Molecular Biology
AUTHOR UNKNOWN, 0
Genome rearrangement by the double cut and join operation.
Friedberg R, Darling AE, Yancopoulos S., Methods Mol. Biol. 452(), 2008
PMID: 18566774
Genome rearrangements and sorting by reversals
AUTHOR UNKNOWN, 1993
The solution space of sorting by DCJ.
Braga MD, Stoye J., J. Comput. Biol. 17(9), 2010
PMID: 20874401
Transforming Men Into Mice (Polynomial Algorithm for Genomic Distance Problem)
AUTHOR UNKNOWN, 1995
The Inversion Distance Problem
AUTHOR UNKNOWN, 2005
Restricted DCJ-indel model: sorting linear genomes with DCJ and indels.
da Silva PH, Machado R, Dantas S, Braga MD., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281630
DCJ-Indel sorting revisited
AUTHOR UNKNOWN, 2013
Restricted DCJ model: rearrangement problems with chromosome reincorporation.
Kovac J, Warren R, Braga MD, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899428

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 24564182
PubMed | Europe PMC

Search this title in

Google Scholar