Group Name

Human Population Genomics


There is common consensus amongst most researchers that the human species originated in Africa. Then how have we populated all the corners of the planet? It turns that there is sufficient history carried in the genomes of individuals to reconstruct some, if not all, of these movements. This requires careful sampling of extant populations of the different geographic regions and even more meticulous analysis to unravel these histories. This work is part of the Genographic Project.

Ancestral Recombinations Graphs at Genomic Scales

Identification of Recombinations in Sequences (IRiS)

Genetic recombinations play a key role in shaping the chromosomal landscapes. The structure that captures these genetic events as the common evolutionary history of a set samples is called an ancestral recombinations graph (ARG) in population genetics literature. The statistical and combinatoric tools for identification of recombinations in sequences (IRiS) presented here is part of the RecoProject (a pilot in Genogrpahic), initiated by Laxmi Parida and Jaume Bertranpetit. The reconstructed ARG of a collection of samples is necessarily a subgraph of the true ARG, hence we call it a subARG.


Brief Description

Given a collection of haplotypes, IRiS produces a subARG in two phases. A combinatorial algorithm called the DSR [8] is a model-based approach to detecting recombinations in haplotypes (with a guaranteed approximation factor [6]). The algorithm is based on iteratively classifying sets of lineages as dominant, subdominant or recombinant (DSR). In the first phase, DSR is run multiple times with different sets of parameters and statistical consensus [5] is derived from them to produce a matrix of recombination information called the recomatrix. This encodes the local topology information of only the high confidence recombination events detected in the first phase. The subARG is constructed from the recomatrix in the second phase [1].

The construction of the ARG at a genomic scale naturally raises the question of reconstructability in general. To understand this aspect of the problem, we have modeled the ARG as a random graph [8]. This lead to the identification of a small structure termed the minimal descriptor of an ARG [9,10].


Accuracy: The reconstructed ARG is superimposed on the true ARG of Cosi simulation.
Left: the red nodes show the extracted recombination nodes after Phase 1. Right: The red nodes and branches superimposed on the true ARG. Notice the increase in density of the reconstructed nodes (and edges) after Phase 2.
(Images generated by Marc Pybus & Asif Javed using Pajek; click on the images for the high definition versions)


Based on IRiS Analysis.


Performance: Running time and memory requirements are shown here. Chr denotes the number of chromosome samples.Top: Phase 1. Middle: Phase 2. Bottom: Both phases. In each plot, the dark line shows the average value and the dotted lines span the ninety percentile of the values.

Executables

The Windows (version), Linux (version) are downloadable here. Also, User Manual.

Related Publications

Application (on population studies)

Download data used in these papers here.
  1. Javed, A., Mel, M., Pybus, M., Zalloua, P., Haber, M., Comas, D., Netea, M., Balanovsky, O., Balanovska, E., Jin, L., Yang, Y., Arunkumar G., Pitchappan, R.M., Bertranpetit, J., Calafell, F., Parida, L., and The Genographic Consortium, Recombination networks as genetic markers: a human variation study of the Old World, Human Genetics, 2011

  2. Mel, M., Javed, A., Pybus, M., Zalloua, P., Haber, M., Comas, D., Netea, M., Balanovsky, O., Balanovska, E., Jin, L., Yang, Y., Pitchappan, R.M., Arunkumar G., Parida, L., Calafell, F., Bertranpetit J., and The Genographic Consortium, Recombination gives a new insight in the effective population size and the history of the Old World human populations, Molecular Biology and Evolution, 2011

  3. Mel, M., Incorporating recombination into the study of Recent Human Evolutionary History, Evolutionary Biology Institute, Pompeu Fabra University, PhD Thesis, March 2011

Methods/Algorithmics

  1. Javed, A., Pybus, M., Mel, M., Utro, F., Bertranpetit, J., Calafell, F., and Parida, L., IRiS: Construction of ARG network at genomic scales, Bioinformatics, 2011

  2. Mel, M., Javed, A., Pybus, M., Calafell, F., Parida, L., Bertranpetit, J., and The Genographic Consortium, A New Method to Reconstruct Recombination Events at a Genomic Scale, PLoS Computational Biology, vol 6, No 11, pp e1001010, 2010

  3. Parida, L., Javed, A., Mel, M., Calafell, F., Bertranpetit, J., and The Genographic Consortium, Minimizing recombinations in consensus networks for phylogeographic studies, BMC Bioinformatics , APBC, Beijing, 2009

  4. Parida, L., Javed, A., Mel, M., and Bertranpetit, J., A case for Recombinomics, IBM Technical Report RC24677, August, 2008

  5. Parida, L., Mel, M., Calafell, F., Bertranpetit, J., and The Genographic Consortium, Estimating the Ancestral Recombinations Graph (ARG) as compatible networks of SNP Patterns, Journal of Computational Biology, vol 15, No 9, pp 1--22, 2008

Theory/Modeling

  1. Utro, F., Pybus, M., and Parida, L., Sum of parts is greater than the whole: inference of common genetic history of populations, BMC Genomics, APBC, Vancouver, Canada, 2013

  2. Parida, L., Palamara, P.F., and Javed, A., A Minimal Descriptor of an Ancestral Recombinations Graph, BMC Bioinformatics, APBC, Inchon, Korea, 2011

  3. Parida, L., Ancestral Recombinations Graph: A Reconstructability Perspective using Random-Graphs Framework, Journal of Computational Biology, vol 17, No 10, pp 1345--1370, 2010

Expositions

  1. Parida, L., Non-redundant Representation of Ancestral Recombinations Graphs, Evolutionary genomics: statistical and computational methods, Editor: Maria Anisimova, Methods in Molecular Biology (Springer) 2011

  2. Javed, A., and Parida, L., Recombinomics: Population Genomics from a Recombination Perspective , Proceedings of C3S2E, Montreal, No 9, pp 129--137, 2010

  3. Parida, L., Graph Model of Coalescence with Recombinations, The Problem Solving Handbook for Computational Biology and Bioinformatics (Lecture notes in mathematics) (Springer Verlag) 2010