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

Algorithms for Molecular Biology

Poly H da Silva²  Raphael Machado²  Simone Dantas¹  Marília DV Braga² 

[1] IME, Universidade Federal Fluminense, Niterói, Brazil

[2] Inmetro – Instituto Nacional de Metrologia, Qualidade e Tecnologia, Duque de Caxias, Brazil

关键词: Algorithms;    Combinatorics;    Comparative genomics;    Evolution;    Genomic distance;    Genome rearrangements;    Substitution;    Insertions and deletions (indels);    Double cut and join (DCJ);   

Others  :  793226
DOI  :  10.1186/1748-7188-8-21

 received in 2012-12-21, accepted in 2013-06-29,  发布年份 2013

【 摘 要 】

Background

Classical approaches to compute the genomic distance are usually limited to genomes with the same content and take into consideration only rearrangements that change the organization of the genome (i.e. positions and orientation of pieces of DNA, number and type of chromosomes, etc.), such as inversions, translocations, fusions and fissions. These operations are generically represented by the double-cut and join (DCJ) operation. The distance between two genomes, in terms of number of DCJ operations, can be computed in linear time. In order to handle genomes with distinct contents, also insertions and deletions of fragments of DNA – named indels – must be allowed. More powerful than an indel is a substitution of a fragment of DNA by another fragment of DNA. Indels and substitutions are called content-modifying operations. It has been shown that both the DCJ-indel and the DCJ-substitution distances can also be computed in linear time, assuming that the same cost is assigned to any DCJ or content-modifying operation.

Results

In the present study we extend the DCJ-indel and the DCJ-substitution models, considering that the content-modifying cost is distinct from and upper bounded by the DCJ cost, and show that the distance in both models can still be computed in linear time. Although the triangular inequality can be disrupted in both models, we also show how to efficiently fix this problem a posteriori.

【 授权许可】

   
2013 da Silva et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 1.

Figure 1.

Figure 1.

Figure 1.

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

【 参考文献 】

• [1]Hannenhalli S, Pevzner P: Transforming men into mice (polynomial algorithm for genomic distance problem). 36th Annual IEEE Symposium on Foundations of Computer Science. 1995, 581-592.
• [2]Yancopoulos S, Attie O, Friedberg R: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 2005, 21:3340-3346.
• [3]Bergeron A, Mixtacki J, Stoye J: A unifying view of genome rearrangements. In Algorithms in Bioinformatics, Lecture Notes in Computer Science, Volume 4175.. Springer; 2006:163-173.
• [4]El-Mabrouk N: Sorting signed permutations by reversals and insertions/deletions of contiguous segments. J Discrete Algorithms 2001, 1:105-122.
• [5]Hannenhalli S, Pevzner P: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 1999, 46:1-27.
• [6]Yancopoulos S, Friedberg R: DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J Comput Biol 2009, 16(10):1311-1338.
• [7]Braga MDV, Willing E, Stoye J: Double Cut and Join with Insertions and Deletions. J Comput Biol 2011, 18(9):1167-1184. (a preliminary version appeared in proceedings of WABI 2010, LNBI vol. 6293, p. 90–101)
• [8]Braga MDV, Machado R, Ribeiro LC, Stoye J: Genomic distance under gene substitutions. BMC Bioinformatics 2011, 12(Suppl 9):S8. BioMed Central Full Text
• [9]Boore JL: The duplication/random loss model for gene rearrangement exemplified by mitochondrial genomes of deuterostome animals. In Comparative Genomics, Volume 1.. Springer; 2000:133-147.
• [10]Moritz C, Dowling TE, Brown WM: Evolution of animal mitochondrial DNA: relevance for population biology and systematics. In Annual Review of Ecology and Systematics, Volume 18.. Annual Reviews Inc; 1987:269-292.
• [11]Blanc G, Ogata H, Robert C, et al.: Reductive genome evolution from the mother of Rickettsia. PLoS Genet 2007, 3:e14.
• [12]Braga MDV, Machado R, Ribeiro LC, Stoye J: On the weight of indels in genomic distances. BMC Bioinformatics 2011, 12(Suppl 9):S13. BioMed Central Full Text
• [13]da Silva PH, Braga MDV, Machado R, Dantas S: DCJ-indel distance with distinct operation costs. In Algorithms in Bioinformatics, Lecture Notes in Computer Science, Volume 7534.. Springer; 2012:378-390.
• [14]Braga MDV, Stoye J: The solution space of sorting by DCJ. J Comput Biol 2010, 17(9):1145-1165.