Linearization of ancestral multichromosomal genomes

Manuch J, Patterson M, Wittler R, Chauve C, Tannier E (2012)
BMC Bioinformatics 13(Proc. of RECOMB-CG 2012).

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ; ;
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.
Publishing Year
ISSN
PUB-ID

Cite this

Manuch J, Patterson M, Wittler R, Chauve C, Tannier E. Linearization of ancestral multichromosomal genomes. BMC Bioinformatics. 2012;13(Proc. of RECOMB-CG 2012).
Manuch, J., Patterson, M., Wittler, R., Chauve, C., & Tannier, E. (2012). Linearization of ancestral multichromosomal genomes. BMC Bioinformatics, 13(Proc. of RECOMB-CG 2012).
Manuch, J., Patterson, M., Wittler, R., Chauve, C., and Tannier, E. (2012). Linearization of ancestral multichromosomal genomes. BMC Bioinformatics 13.
Manuch, J., et al., 2012. Linearization of ancestral multichromosomal genomes. BMC Bioinformatics, 13(Proc. of RECOMB-CG 2012).
J. Manuch, et al., “Linearization of ancestral multichromosomal genomes”, BMC Bioinformatics, vol. 13, 2012.
Manuch, J., Patterson, M., Wittler, R., Chauve, C., Tannier, E.: Linearization of ancestral multichromosomal genomes. BMC Bioinformatics. 13, (2012).
Manuch, Jan, Patterson, Murray, Wittler, Roland, Chauve, Cedric, and Tannier, Eric. “Linearization of ancestral multichromosomal genomes”. BMC Bioinformatics 13.Proc. of RECOMB-CG 2012 (2012).
This data publication is cited in the following publications:
This publication cites the following data publications:

11 References

Data provided by Europe PubMed Central.

Reconstructing contiguous regions of an ancestral genome.
Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, Blanchette M, Haussler D, Miller W., Genome Res. 16(12), 2006
PMID: 16983148
Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes.
Muffato M, Louis A, Poisnel CE, Roest Crollius H., Bioinformatics 26(8), 2010
PMID: 20185404
A unified approach for reconstructing ancient gene clusters.
Stoye J, Wittler R., IEEE/ACM Trans Comput Biol Bioinform 6(3), 2009
PMID: 19644167
ANGES: reconstructing ANcestral GEnomeS maps.
Jones BR, Rajaraman A, Tannier E, Chauve C., Bioinformatics 28(18), 2012
PMID: 22820205
DUPCAR: reconstructing contiguous ancestral regions with duplications.
Ma J, Ratan A, Raney BJ, Suh BB, Zhang L, Miller W, Haussler D., J. Comput. Biol. 15(8), 2008
PMID: 18774902
Evolution of gene neighborhoods within reconciled phylogenies.
Berard S, Gallien C, Boussau B, Szollosi GJ, Daubin V, Tannier E., Bioinformatics 28(18), 2012
PMID: 22962456
Dynamics of genome rearrangement in bacterial populations.
Darling AE, Miklos I, Ragan MA., PLoS Genet. 4(7), 2008
PMID: 18650965
Phylogenetic comparative assembly.
Husemann P, Stoye J., Algorithms Mol Biol 5(), 2010
PMID: 20047659
Genome assembly reborn: recent computational challenges.
Pop M., Brief. Bioinformatics 10(4), 2009
PMID: 19482960
Comparing genomes with duplications: a computational complexity point of view.
Blin G, Chauve C, Fertin G, Rizzi R, Vialette S., IEEE/ACM Trans Comput Biol Bioinform 4(4), 2007
PMID: 17975264

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 23281593
PubMed | Europe PMC

Search this title in

Google Scholar