Affichage des résultats 5301 à 5320 sur 7048 au total
Wandrille Duchemin, Vincent Daubin, Eric Tannier
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. I also give a preliminary result on a method for generating these binary matrices of degree 2, i.e., a method for inferring ancestral adjacencies, and how the Linearization Problem fits into this larger context.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.
Emeric Figuet, Marion Ballenghien, Nicolas Lartillot, Nicolas Galtier
Samuel Drulhe, Giancarlo Ferrari-Trecate, Hidde de Jong, Alain Viari
Céline Martin, Bruno Maureille, Romain Amiot, Alexandra Touzeau, Aurélien Royer, François Fourel, Gérard Panczer, Jean-Pierre Flandrois, Christophe Lécuyer
L. G. Halsey, Y. Handrich, B. Rey, A. Fahlman, A. J. Woakes, P. J. Butler
L.G. Halsey, Y. Handrich, B. Rey, A. Fahlman, A.J. Woakes, P.J. Butler
Wandrille Duchemin, Guillaume Gence, Anne-Muriel Arigon Chifolleau, Lars Arvestad, Mukul Bansal, Vincent Berry, Bastien Boussau, François Chevenet, Nicolas Comte, Adrián Davín, Christophe Dessimoz, David Dylus, Damir Hasic, Diego Mallo, Rémi Planel, David Posada, Celine Scornavacca, Gergely Szöllősi, Louxin Zhang, Eric Tannier, Vincent Daubin
F. Planchamp, K.-A. Nguyen, T. Vial, S. Nasri, E. Javouhey, Y. Gillet, B. Ranchin, F. Villard, D. Floret, P. Cochat, François Gueyffier, Behrouz Kassai
Dexiong Chen, Laurent Jacob, Julien Mairal
Loïc Palumbo, Sebastien Caron, Jean-Marie Ballouard, Xavier Bonnet, Eve Ramery, Emmanuelle Gilot-Fromont, Sylvain Larrat
D. Gensburger, S. Boutroy, R. Chapurlat, R. Nove-Josserand, S. Roche, Muriel Rabilloud, I. Durieu
Cécile Vanpé, Lucie Debeffe, A. J. Mark Hewison, Erwan Quéméré, Jean-François Lemaître, Maxime Galan, Britany Amblard, François Klein, Bruno Cargnelutti, Gilles Capron, Joel Merlet, Claude Warnant, Jean-Michel Gaillard
Jean-Marie Delpuech, J. Meyet
Bérénice Batut, Carole Knibbe, Gabriel Marais, Vincent Daubin
Raluca Uricaru, Guillaume Rizk, Vincent Lacroix, Elsa Quillery, Olivier Plantard, Rayan Chikhi, Claire Lemaitre, Pierre Peterlongo
Catherine Cornu, Anne Donche, Carine Coffre, Amélie Le Gouge, Boulkedid Rym, Isabelle Vaugier, Frédéric Barbot, Alain Leizorovicz, Nadine Juge, Céline Giraud, François Gueyffier, Alexandra Félin, Thibault Mura, Hugues Chevassus, Christine Binquet, Comité de Pilotage Du Groupe de Travail Harmonisation Des Procédures de Réseau Des Cic
Chiara Barbieri, Alexander Hübner, Enrico Macholdt, Shengyu Ni, Sebastian Lippold, Roland Schröder, Sununguko W. Mpoloka, Josephine Purps, Lutz Roewer, Mark Stoneking, Brigitte Pakendorf