On the Inversion-Indel Distance

Willing E, Zaccaria S, Dias Vieira Braga M, Stoye J (2013)
BMC Bioinformatics 14(Suppl 15: Proc. of RECOMB-CG 2013): S3.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
Autor/in
; ; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
2013
Zeitschriftentitel
BMC Bioinformatics
Band
14
Ausgabe
Suppl 15: Proc. of RECOMB-CG 2013
Art.-Nr.
S3
eISSN
1471-2105
Page URI
https://pub.uni-bielefeld.de/record/2611630

Zitieren

Willing E, Zaccaria S, Dias Vieira Braga M, Stoye J. On the Inversion-Indel Distance. BMC Bioinformatics. 2013;14(Suppl 15: Proc. of RECOMB-CG 2013): S3.
Willing, E., Zaccaria, S., Dias Vieira Braga, M., & Stoye, J. (2013). On the Inversion-Indel Distance. BMC Bioinformatics, 14(Suppl 15: Proc. of RECOMB-CG 2013), S3. doi:10.1186/1471-2105-14-S15-S3
Willing, E., Zaccaria, S., Dias Vieira Braga, M., and Stoye, J. (2013). On the Inversion-Indel Distance. BMC Bioinformatics 14:S3.
Willing, E., et al., 2013. On the Inversion-Indel Distance. BMC Bioinformatics, 14(Suppl 15: Proc. of RECOMB-CG 2013): S3.
E. Willing, et al., “On the Inversion-Indel Distance”, BMC Bioinformatics, vol. 14, 2013, : S3.
Willing, E., Zaccaria, S., Dias Vieira Braga, M., Stoye, J.: On the Inversion-Indel Distance. BMC Bioinformatics. 14, : S3 (2013).
Willing, Eyla, Zaccaria, Simone, Dias Vieira Braga, Marília, and Stoye, Jens. “On the Inversion-Indel Distance”. BMC Bioinformatics 14.Suppl 15: Proc. of RECOMB-CG 2013 (2013): S3.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T09:18:17Z
MD5 Prüfsumme
720d4fcc84b54b895d50ff72cc6623f4

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 24564182
PubMed | Europe PMC

Suchen in

Google Scholar