Minimizing recombinations in consensus networks for phylogeographic studies
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 segmentof the human Chromosome X data we are able to infer ancient recombinations, populationspecific recombinations and more, which also support the widely accepted Out of Africamodel. 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.Conclusions: 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.
Laxmi Parida Asif Javed Marta Melé Francesc Calafel Jaume Bertranpeti Genographic Consortium
Computational Biology Center, IBM T J Watson Research, Yorktown, USA Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA Work done during an Biologia Evolutiva, Universitat Pompeu Fabra, Barcelona, Catalonia, Spain Work done during an intern Biologia Evolutiva, Universitat Pompeu Fabra, Barcelona, Catalonia, Spain
国际会议
The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)
北京
英文
811-822
2009-01-01（万方平台首次上网日期，不代表论文的发表时间）