To access the full text documents, please follow this link:

Minimizing recombinations in consensus networks for phylogeographic studies
Parida, Laxmi; Javed, Asif; Melé Messeguer, Marta; Calafell i Majó, Francesc; Bertranpetit, Jaume; Genographic Consortium
Background: We address the problem of studying recombinational variations in (human) populations. In this paper, our focus is on one computational aspect of the general task: Given two networks G1 and G2, with both mutation and recombination events, defined on overlapping sets of extant units the objective is to compute a consensus network G3 with minimum number of additional recombinations. We describe a polynomial time algorithm with a guarantee that the number of computed new recombination events is within ϵ = sz(G1, G2) (function sz is a well-behaved function of the sizes and topologies of G1 and G2) of the optimal number of recombinations. To date, this is the best known result for a network consensus problem.Results: Although the network consensus problem can be applied to a variety of domains, here we focus on structure of human populations. With our preliminary analysis on a segment of the human Chromosome X data we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. These results have been verified independently using traditional manual procedures. To the best of our knowledge, this is the first recombinations-based characterization of human populations. Conclusion: We show that our mathematical model identifies recombination spots in the individual haplotypes; the aggregate of these spots over a set of haplotypes defines a recombinational landscape that has enough signal to detect continental as well as population divide based on a short segment of Chromosome X. In particular, we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. The agreement with mutation-based analysis can be viewed as an indirect validation of our results and the model. Since the model in principle gives us more information embedded in the networks, in our future work, we plan to investigate more non-traditional questions via these structures computed by our methodology.
Genètica de poblacions
Recombinació genètica
(c) 2009 Parida et al. Creative Commons Attribution License
BioMed Central

Show full item record

Related documents

Other documents of the same author

Marigorta, Urko M.; Lao Grueso, Oscar; Casals López, Ferran; Calafell i Majó, Francesc; Morcillo Suárez, Carlos; Faria, Rui; Bosch Fusté, Elena; Serra, François; Bertranpetit, Jaume; Dopazo, Hernán; Navarro i Cuartiellas, Arcadi, 1969-
Bosch Fusté, Elena; Laayouni, Hafid; Morcillo Suárez, Carlos; Casals, Ferran; Moreno Estrada, Andrés; Ferrer Admetlla, Anna; Gardner, Michelle; Rosa, Araceli; Comas, David; Graffelman, Jan; Calafell i Majó, Francesc; Bertranpetit, Jaume
Mendizábal, Isabel; Sandoval Mendoza, Karla; Berniell Lee, Gemma; Calafell i Majó, Francesc; Salas, Antonio; Martínez Fuentes, Antonio; Comas, David
Kalaydjieva, Luba; Gresham, David; Calafell i Majó, Francesc
Moreno Estrada, Andrés; Bosch Fusté, Elena; Stoneking, Mark; Bertranpetit, Jaume; Calafell, Francesc; Navarro i Cuartiellas, Arcadi, 1969-; Casals, Ferran; Tang, Kun; Marquès i Bonet, Tomàs, 1975-; Sikora, Martin