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

The graph GΠΠ of a genome Π. Π is a genome on the set of genes {1,...,14}, containing three chromosomes, two of them being linear and one circular. Its adjacencies are the union of C1 = {12h4h, 4t14t, 14h1t, 1h7h, 7t8t}, C2 = {3t11t, 11h10t, 10h6t, 6h13h, 13t3h} and C3 = {9h2t, 2h5h}. It has four telomeres.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: The graph GΠΠ of a genome Π. Π is a genome on the set of genes {1,...,14}, containing three chromosomes, two of them being linear and one circular. Its adjacencies are the union of C1 = {12h4h, 4t14t, 14h1t, 1h7h, 7t8t}, C2 = {3t11t, 11h10t, 10h6t, 6h13h, 13t3h} and C3 = {9h2t, 2h5h}. It has four telomeres.

Mentions: We follow the general formulation of a genome in [3]. A gene A is an oriented sequence of DNA, identified by its tail At and its head Ah. Tails and heads are the extremities of the genes. An adjacency is an unordered pair of gene extremities. A genome Π is a set of adjacencies on a set of genes. Each adjacency in a genome means that two gene extremities are consecutive on the DNA molecule. In a genome, each gene extremity is adjacent to zero or one other extremity. An extremity x that is not adjacent to any other extremity is called a telomere, and can be written as an adjacency x∘ with a symbol ∘. The adjacency x∘ is called a telomeric adjacency. For a genome Π on a set of genes , consider the graph GΠ whose vertices are all the extremities of the genes, and the edges include all the non telomeric adjacencies in Π as well as an edge joining the head and the tail of each gene. This graph is a set of disjoint paths and cycles. Every connected component is called a chromosome of Π. A chromosome is linear if it is a path, and circular if it is a cycle. A genome with only linear, or only circular, chromosomes is called a linear or circular genome, respectively. An example of a graph GΠ is given in Figure 1.


Multichromosomal median and halving problems under different genomic distances.

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

The graph GΠΠ of a genome Π. Π is a genome on the set of genes {1,...,14}, containing three chromosomes, two of them being linear and one circular. Its adjacencies are the union of C1 = {12h4h, 4t14t, 14h1t, 1h7h, 7t8t}, C2 = {3t11t, 11h10t, 10h6t, 6h13h, 13t3h} and C3 = {9h2t, 2h5h}. It has four telomeres.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: The graph GΠΠ of a genome Π. Π is a genome on the set of genes {1,...,14}, containing three chromosomes, two of them being linear and one circular. Its adjacencies are the union of C1 = {12h4h, 4t14t, 14h1t, 1h7h, 7t8t}, C2 = {3t11t, 11h10t, 10h6t, 6h13h, 13t3h} and C3 = {9h2t, 2h5h}. It has four telomeres.
Mentions: We follow the general formulation of a genome in [3]. A gene A is an oriented sequence of DNA, identified by its tail At and its head Ah. Tails and heads are the extremities of the genes. An adjacency is an unordered pair of gene extremities. A genome Π is a set of adjacencies on a set of genes. Each adjacency in a genome means that two gene extremities are consecutive on the DNA molecule. In a genome, each gene extremity is adjacent to zero or one other extremity. An extremity x that is not adjacent to any other extremity is called a telomere, and can be written as an adjacency x∘ with a symbol ∘. The adjacency x∘ is called a telomeric adjacency. For a genome Π on a set of genes , consider the graph GΠ whose vertices are all the extremities of the genes, and the edges include all the non telomeric adjacencies in Π as well as an edge joining the head and the tail of each gene. This graph is a set of disjoint paths and cycles. Every connected component is called a chromosome of Π. A chromosome is linear if it is a path, and circular if it is a cycle. A genome with only linear, or only circular, chromosomes is called a linear or circular genome, respectively. An example of a graph GΠ is given in Figure 1.

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