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

da Silva PH, Machado R, Dantas S, Braga MD - BMC Bioinformatics (2012)

Bottom Line: However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation.When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model.The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.

View Article: PubMed Central - HTML - PubMed

Affiliation: IME, Universidade Federal Fluminense, Niterói, Brazil. poly.hannah@gmail.com

ABSTRACT

Background: The double-cut-and-join (DCJ) is a model that is able to efficiently sort a genome into another, generalizing the typical mutations (inversions, fusions, fissions, translocations) to which genomes are subject, but allowing the existence of circular chromosomes at the intermediate steps. In the general model many circular chromosomes can coexist in some intermediate step. However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation. These two consecutive DCJ operations, which create and reincorporate a circular chromosome, mimic a transposition or a block-interchange. When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model. If the genomes have unequal contents, in addition to DCJ it is necessary to consider indels, which are insertions and deletions of DNA segments. Linear time algorithms were proposed to compute the distance and to find a sorting scenario in a general, unrestricted DCJ-indel model that considers DCJ and indels.

Results: In the present work we consider the restricted DCJ-indel model for sorting linear genomes with unequal contents. We allow DCJ operations and indels with the following constraint: if a circular chromosome is created by a DCJ, it has to be reincorporated in the next step (no other DCJ or indel can be applied between the creation and the reincorporation of a circular chromosome). We then develop a sorting algorithm and give a tight upper bound for the restricted DCJ-indel distance.

Conclusions: We have given a tight upper bound for the restricted DCJ-indel distance. The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.

Show MeSH

Related in: MedlinePlus

The rooted tree of an accumulation of a -run is built from the leafs to the root (bottom to up). Inversely, the rooted tree of an inverted-split of a -run is built from the root to the leafs (top to down).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3526439&req=5

Figure 8: The rooted tree of an accumulation of a -run is built from the leafs to the root (bottom to up). Inversely, the rooted tree of an inverted-split of a -run is built from the root to the leafs (top to down).

Mentions: As an example, take v1 = γ1ℓ1γ2, x1 = γ2γ3, v2 = γ3ℓ2γ4, x2 = γ4γ5, v3 = γ5ℓ3γ6, x3 = γ6γ7, v4 = γ7ℓ4γ8, with all ℓk ≠ ε and let r1 = v1x1v2x2v3x3v4 be a -run. We can start the accumulation with a DCJ of type on partners v2 and v3, creating v2-3 = γ3ℓ2ℓ3γ6 and γ4γ5, reducing r1 to r2 = v1x1v2-3x3v4. We then apply another DCJ of type on partners v1 and v2-3, creating v1-2-3 = γ1ℓ1ℓ2ℓ3γ6 and γ2γ3, reducing r2 to r3 = v1-2-3x3v4. Finally, we apply a DCJ of type on partners v1-2-3 and v4, creating v1-2-3-4 = γ1ℓ1ℓ2ℓ3ℓ4γ8 and γ6γ7, reducing r3 to r4 = v1-2-3-4. If we follow the accumulation of a run, considering only the labeled vertices, we obtain a rooted tree that is built from the leafs to the root (see Figure 8). The root of the tree indicates the possible positions of a deletion.


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

da Silva PH, Machado R, Dantas S, Braga MD - BMC Bioinformatics (2012)

The rooted tree of an accumulation of a -run is built from the leafs to the root (bottom to up). Inversely, the rooted tree of an inverted-split of a -run is built from the root to the leafs (top to down).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3526439&req=5

Figure 8: The rooted tree of an accumulation of a -run is built from the leafs to the root (bottom to up). Inversely, the rooted tree of an inverted-split of a -run is built from the root to the leafs (top to down).
Mentions: As an example, take v1 = γ1ℓ1γ2, x1 = γ2γ3, v2 = γ3ℓ2γ4, x2 = γ4γ5, v3 = γ5ℓ3γ6, x3 = γ6γ7, v4 = γ7ℓ4γ8, with all ℓk ≠ ε and let r1 = v1x1v2x2v3x3v4 be a -run. We can start the accumulation with a DCJ of type on partners v2 and v3, creating v2-3 = γ3ℓ2ℓ3γ6 and γ4γ5, reducing r1 to r2 = v1x1v2-3x3v4. We then apply another DCJ of type on partners v1 and v2-3, creating v1-2-3 = γ1ℓ1ℓ2ℓ3γ6 and γ2γ3, reducing r2 to r3 = v1-2-3x3v4. Finally, we apply a DCJ of type on partners v1-2-3 and v4, creating v1-2-3-4 = γ1ℓ1ℓ2ℓ3ℓ4γ8 and γ6γ7, reducing r3 to r4 = v1-2-3-4. If we follow the accumulation of a run, considering only the labeled vertices, we obtain a rooted tree that is built from the leafs to the root (see Figure 8). The root of the tree indicates the possible positions of a deletion.

Bottom Line: However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation.When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model.The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.

View Article: PubMed Central - HTML - PubMed

Affiliation: IME, Universidade Federal Fluminense, Niterói, Brazil. poly.hannah@gmail.com

ABSTRACT

Background: The double-cut-and-join (DCJ) is a model that is able to efficiently sort a genome into another, generalizing the typical mutations (inversions, fusions, fissions, translocations) to which genomes are subject, but allowing the existence of circular chromosomes at the intermediate steps. In the general model many circular chromosomes can coexist in some intermediate step. However, when the compared genomes are linear, it is more plausible to use the so-called restricted DCJ model, in which we proceed the reincorporation of a circular chromosome immediately after its creation. These two consecutive DCJ operations, which create and reincorporate a circular chromosome, mimic a transposition or a block-interchange. When the compared genomes have the same content, it is known that the genomic distance for the restricted DCJ model is the same as the distance for the general model. If the genomes have unequal contents, in addition to DCJ it is necessary to consider indels, which are insertions and deletions of DNA segments. Linear time algorithms were proposed to compute the distance and to find a sorting scenario in a general, unrestricted DCJ-indel model that considers DCJ and indels.

Results: In the present work we consider the restricted DCJ-indel model for sorting linear genomes with unequal contents. We allow DCJ operations and indels with the following constraint: if a circular chromosome is created by a DCJ, it has to be reincorporated in the next step (no other DCJ or indel can be applied between the creation and the reincorporation of a circular chromosome). We then develop a sorting algorithm and give a tight upper bound for the restricted DCJ-indel distance.

Conclusions: We have given a tight upper bound for the restricted DCJ-indel distance. The question whether this bound can be reduced so that both the general and the restricted DCJ-indel distances are equal remains open.

Show MeSH
Related in: MedlinePlus