Limits...
Linearization of ancestral multichromosomal genomes.

Maňuch J, Patterson M, Wittler R, Chauve C, Tannier E - BMC Bioinformatics (2012)

Bottom Line: This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes.Algorithms can also be used as heuristics for hard variants.More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.

View Article: PubMed Central - HTML - PubMed

Affiliation: INRIA Rhône-Alpes, 655 avenue de I'Europe, F-38344 Montbonnot, France. Murray.Patterson@inria.fr

ABSTRACT

Background: Recovering the structure of ancestral genomes can be formalized in terms of properties of binary matrices such as the Consecutive-Ones Property (C1P). The Linearization Problem asks to extract, from a given binary matrix, a maximum weight subset of rows that satisfies such a property. This problem is in general intractable, and in particular if the ancestral genome is expected to contain only linear chromosomes or a unique circular chromosome. In the present work, we consider a relaxation of this problem, which allows ancestral genomes that can contain several chromosomes, each either linear or circular.

Result: We show that, when restricted to binary matrices of degree two, which correspond to adjacencies, the genomic characters used in most ancestral genome reconstruction methods, this relaxed version of the Linearization Problem is polynomially solvable using a reduction to a matching problem. This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes. We also prove that for matrices with rows of degrees 2 and 3, without multiplicity and without weights on the rows, the problem is NP-complete, thus tracing sharp tractability boundaries.

Conclusion: As it happened for the breakpoint median problem, also used in ancestral genome reconstruction, relaxing the definition of a genome turns an intractable problem into a tractable one. The relaxation is adapted to some biological contexts, such as bacterial genomes with several replicons, possibly partially assembled. Algorithms can also be used as heuristics for hard variants. More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.

Show MeSH

Related in: MedlinePlus

The only possible configuration of a 2-clause gadget without expected behavior and the corresponding transformation.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 9: The only possible configuration of a 2-clause gadget without expected behavior and the corresponding transformation.

Mentions: Secondly, in the valid covering of Hϕ we can assume, by Corollary 1, that exactly one hyperedge is removed from each 2-clause gadget. Assume now that a 2-clause gadget is not expected behavior covered. The only possible such configuration can be transformed to the expected behavior covering as shown in Figure 9. Again, these local transformations do not affect validity of the covering.


Linearization of ancestral multichromosomal genomes.

Maňuch J, Patterson M, Wittler R, Chauve C, Tannier E - BMC Bioinformatics (2012)

The only possible configuration of a 2-clause gadget without expected behavior and the corresponding transformation.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 9: The only possible configuration of a 2-clause gadget without expected behavior and the corresponding transformation.
Mentions: Secondly, in the valid covering of Hϕ we can assume, by Corollary 1, that exactly one hyperedge is removed from each 2-clause gadget. Assume now that a 2-clause gadget is not expected behavior covered. The only possible such configuration can be transformed to the expected behavior covering as shown in Figure 9. Again, these local transformations do not affect validity of the covering.

Bottom Line: This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes.Algorithms can also be used as heuristics for hard variants.More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.

View Article: PubMed Central - HTML - PubMed

Affiliation: INRIA Rhône-Alpes, 655 avenue de I'Europe, F-38344 Montbonnot, France. Murray.Patterson@inria.fr

ABSTRACT

Background: Recovering the structure of ancestral genomes can be formalized in terms of properties of binary matrices such as the Consecutive-Ones Property (C1P). The Linearization Problem asks to extract, from a given binary matrix, a maximum weight subset of rows that satisfies such a property. This problem is in general intractable, and in particular if the ancestral genome is expected to contain only linear chromosomes or a unique circular chromosome. In the present work, we consider a relaxation of this problem, which allows ancestral genomes that can contain several chromosomes, each either linear or circular.

Result: We show that, when restricted to binary matrices of degree two, which correspond to adjacencies, the genomic characters used in most ancestral genome reconstruction methods, this relaxed version of the Linearization Problem is polynomially solvable using a reduction to a matching problem. This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes. We also prove that for matrices with rows of degrees 2 and 3, without multiplicity and without weights on the rows, the problem is NP-complete, thus tracing sharp tractability boundaries.

Conclusion: As it happened for the breakpoint median problem, also used in ancestral genome reconstruction, relaxing the definition of a genome turns an intractable problem into a tractable one. The relaxation is adapted to some biological contexts, such as bacterial genomes with several replicons, possibly partially assembled. Algorithms can also be used as heuristics for hard variants. More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.

Show MeSH
Related in: MedlinePlus