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.
Suppl 15: Proc. of RECOMB-CG 2013
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):
This Item is protected by copyright and/or related rights. [...]