Limits...
Multichromosomal median and halving problems under different genomic distances.

Tannier E, Zheng C, Sankoff D - BMC Bioinformatics (2009)

Bottom Line: Although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.We list the remaining open problems.This theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes.

View Article: PubMed Central - HTML - PubMed

Affiliation: INRIA Rhône-Alpes, Inovallée, Montbonnot, Saint Ismier Cedex, France. Eric.Tannier@inria.fr

ABSTRACT

Background: Genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor to extant species. Exploring complexity issues is a first step towards devising efficient algorithms. The complexity of the median problem for unichromosomal genomes (permutations) has been settled for both the breakpoint distance and the reversal distance. Although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.

Results: We settle here the complexity of several genome median and halving problems, including a surprising polynomial result for the breakpoint median and guided halving problems in genomes with circular and linear chromosomes, showing that the multichromosomal problem is actually easier than the unichromosomal problem. Still other variants of these problems are NP-complete, including the DCJ double distance problem, previously mentioned as an open question. We list the remaining open problems.

Conclusion: This theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes.

Show MeSH

Related in: MedlinePlus

Reduction of BGD to DCJ double distance problem. The left hand graph is the balanced bicoloured graph G, and the right hand graph represents the adjacencies of the duplicated genomes Δ and Π ⊕ Π. In the case of a degree 2 vertex in G, the adjacencies of Π ⊕ Π are determined, as one solution gives more cycles. In the case of a degree 4 vertex in G, the two possibilities for the adjacencies of Π ⊕ Π are shown (Π ⊕ Π contains either the vertical or horizontal dotted adjacencies).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 6: Reduction of BGD to DCJ double distance problem. The left hand graph is the balanced bicoloured graph G, and the right hand graph represents the adjacencies of the duplicated genomes Δ and Π ⊕ Π. In the case of a degree 2 vertex in G, the adjacencies of Π ⊕ Π are determined, as one solution gives more cycles. In the case of a degree 4 vertex in G, the two possibilities for the adjacencies of Π ⊕ Π are shown (Π ⊕ Π contains either the vertical or horizontal dotted adjacencies).

Mentions: Let G be a balanced bicoloured graph on n vertices, defining an instance of the BGD problem. Let w2 be the number of degree 2 vertices of G, and w4 be the number of degree 4 vertices of G. Define the gene set as the vertex set of G. Construct an all-duplicates genome Δ and a genome Π on in the following way, as illustrated in Figure 6. First, for each gene X of , let XtXh be an adjacency in Π. Then, for every vertex X of G, let X1t, X1h, X2t and X2h, be the extremities of the duplicated gene X. If X has degree two in G, add the adjacency X1tX2h in Δ (if X has degree four, no adjacency is added at this point). Then for each blue edge XY in G, choose among X1h and X2h an extremitiy that is not yet involved in an adjacency, and another among Y1h and Y2h (arbitrarily if neither is involved in an adjacency yet). Add an adjacency between the two chosen extremities in Δ. Then for each red edge XY in G, choose among X1t and X2t an extremitiy that is not yet involved in an adjacency, and another among Y1t and Y2t (arbitrarily if neither is involved in an adjacency yet). Add an adjacency between the two chosen extremities in Δ.


Multichromosomal median and halving problems under different genomic distances.

Tannier E, Zheng C, Sankoff D - BMC Bioinformatics (2009)

Reduction of BGD to DCJ double distance problem. The left hand graph is the balanced bicoloured graph G, and the right hand graph represents the adjacencies of the duplicated genomes Δ and Π ⊕ Π. In the case of a degree 2 vertex in G, the adjacencies of Π ⊕ Π are determined, as one solution gives more cycles. In the case of a degree 4 vertex in G, the two possibilities for the adjacencies of Π ⊕ Π are shown (Π ⊕ Π contains either the vertical or horizontal dotted adjacencies).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 6: Reduction of BGD to DCJ double distance problem. The left hand graph is the balanced bicoloured graph G, and the right hand graph represents the adjacencies of the duplicated genomes Δ and Π ⊕ Π. In the case of a degree 2 vertex in G, the adjacencies of Π ⊕ Π are determined, as one solution gives more cycles. In the case of a degree 4 vertex in G, the two possibilities for the adjacencies of Π ⊕ Π are shown (Π ⊕ Π contains either the vertical or horizontal dotted adjacencies).
Mentions: Let G be a balanced bicoloured graph on n vertices, defining an instance of the BGD problem. Let w2 be the number of degree 2 vertices of G, and w4 be the number of degree 4 vertices of G. Define the gene set as the vertex set of G. Construct an all-duplicates genome Δ and a genome Π on in the following way, as illustrated in Figure 6. First, for each gene X of , let XtXh be an adjacency in Π. Then, for every vertex X of G, let X1t, X1h, X2t and X2h, be the extremities of the duplicated gene X. If X has degree two in G, add the adjacency X1tX2h in Δ (if X has degree four, no adjacency is added at this point). Then for each blue edge XY in G, choose among X1h and X2h an extremitiy that is not yet involved in an adjacency, and another among Y1h and Y2h (arbitrarily if neither is involved in an adjacency yet). Add an adjacency between the two chosen extremities in Δ. Then for each red edge XY in G, choose among X1t and X2t an extremitiy that is not yet involved in an adjacency, and another among Y1t and Y2t (arbitrarily if neither is involved in an adjacency yet). Add an adjacency between the two chosen extremities in Δ.

Bottom Line: Although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.We list the remaining open problems.This theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes.

View Article: PubMed Central - HTML - PubMed

Affiliation: INRIA Rhône-Alpes, Inovallée, Montbonnot, Saint Ismier Cedex, France. Eric.Tannier@inria.fr

ABSTRACT

Background: Genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor to extant species. Exploring complexity issues is a first step towards devising efficient algorithms. The complexity of the median problem for unichromosomal genomes (permutations) has been settled for both the breakpoint distance and the reversal distance. Although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.

Results: We settle here the complexity of several genome median and halving problems, including a surprising polynomial result for the breakpoint median and guided halving problems in genomes with circular and linear chromosomes, showing that the multichromosomal problem is actually easier than the unichromosomal problem. Still other variants of these problems are NP-complete, including the DCJ double distance problem, previously mentioned as an open question. We list the remaining open problems.

Conclusion: This theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes.

Show MeSH
Related in: MedlinePlus