Linearization of ancestral multichromosomal genomes

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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Manuch, Jan; Patterson, Murray; Wittler, RolandUniBi ; Chauve, Cedric; Tannier, Eric
Abstract / Bemerkung
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.
Erscheinungsjahr
2012
Zeitschriftentitel
BMC Bioinformatics
Band
13
Ausgabe
Proc. of RECOMB-CG 2012
Art.-Nr.
S11
ISSN
1471-2105
Page URI
https://pub.uni-bielefeld.de/record/2553300

Zitieren

Manuch J, Patterson M, Wittler R, Chauve C, Tannier E. Linearization of ancestral multichromosomal genomes. BMC Bioinformatics. 2012;13(Proc. of RECOMB-CG 2012): S11.
Manuch, J., Patterson, M., Wittler, R., Chauve, C., & Tannier, E. (2012). Linearization of ancestral multichromosomal genomes. BMC Bioinformatics, 13(Proc. of RECOMB-CG 2012), S11. doi:10.1186/1471-2105-13-S19-S11
Manuch, Jan, Patterson, Murray, Wittler, Roland, Chauve, Cedric, and Tannier, Eric. 2012. “Linearization of ancestral multichromosomal genomes”. BMC Bioinformatics 13 (Proc. of RECOMB-CG 2012): S11.
Manuch, J., Patterson, M., Wittler, R., Chauve, C., and Tannier, E. (2012). Linearization of ancestral multichromosomal genomes. BMC Bioinformatics 13:S11.
Manuch, J., et al., 2012. Linearization of ancestral multichromosomal genomes. BMC Bioinformatics, 13(Proc. of RECOMB-CG 2012): S11.
J. Manuch, et al., “Linearization of ancestral multichromosomal genomes”, BMC Bioinformatics, vol. 13, 2012, : S11.
Manuch, J., Patterson, M., Wittler, R., Chauve, C., Tannier, E.: Linearization of ancestral multichromosomal genomes. BMC Bioinformatics. 13, : S11 (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): S11.

5 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Linearization of Median Genomes Under the Double-Cut-and-Join-Indel Model.
Avdeyev P, Jiang S, Alekseyev MA., Evol Bioinform Online 15(), 2019
PMID: 31217687
Phylogenetic signal from rearrangements in 18 Anopheles species by joint scaffolding extant and ancestral genomes.
Anselmetti Y, Duchemin W, Tannier E, Chauve C, Bérard S., BMC Genomics 19(suppl 2), 2018
PMID: 29764366
Efficient Gene Tree Correction Guided by Genome Evolution.
Noutahi E, Semeria M, Lafond M, Seguin J, Boussau B, Guéguen L, El-Mabrouk N, Tannier E., PLoS One 11(8), 2016
PMID: 27513924
FPSAC: fast phylogenetic scaffolding of ancient contigs.
Rajaraman A, Tannier E, Chauve C., Bioinformatics 29(23), 2013
PMID: 24068034

14 References

Daten bereitgestellt von Europe PubMed Central.

Consistency of sequence-based gene clusters.
Wittler R, Manuch J, Patterson M, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899413
SCJ: a breakpoint-like distance that simplifies several rearrangement problems.
Feijao P, Meidanis J., IEEE/ACM Trans Comput Biol Bioinform 8(5), 2011
PMID: 21339538
ANGES: reconstructing ANcestral GEnomeS maps.
Jones BR, Rajaraman A, Tannier E, Chauve C., Bioinformatics 28(18), 2012
PMID: 22820205
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
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
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
Bayesian sampling of genomic rearrangement scenarios via double cut and join.
Miklos I, Tannier E., Bioinformatics 26(24), 2010
PMID: 21037244
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
Genome assembly reborn: recent computational challenges.
Pop M., Brief. Bioinformatics 10(4), 2009
PMID: 19482960
A unified approach for reconstructing ancient gene clusters.
Stoye J, Wittler R., IEEE/ACM Trans Comput Biol Bioinform 6(3), 2009
PMID: 19644167
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
Yeast ancestral genome reconstructions: the possibilities of computational methods II.
Chauve C, Gavranovic H, Ouangraoua A, Tannier E., J. Comput. Biol. 17(9), 2010
PMID: 20874398
Dynamics of genome rearrangement in bacterial populations.
Darling AE, Miklos I, Ragan MA., PLoS Genet. 4(7), 2008
PMID: 18650965
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Quellen

PMID: 23281593
PubMed | Europe PMC

Suchen in

Google Scholar