MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is meant to be applied to recover historic information from genetic data. The following model, is (probably) the simplest possible which takes recombinations into account.

First, let us introduce some terms:

  • human is a finite set of numbers in (0,1); further these numbers will be called "scars".

  • population is a finite set of humans

One can perform one operation with a population:

  • recombination; i.e. take two humans $A$ and $B$ from the population, choose randomly a number $x\in(0,1)$ and produce a new human $C$ which has scar $x$, all scars in $A$ which are $ < x$ and all scars in $B$ which are $ > x$.

Assume someone starts with a population formed by two empty sets and does these operations for a while then stop. Assume you have all information about a portion of the population, BUT you do not know how this portion had been chousen. What one can say (even in which terms) about the history of population.


  • It is not exactly mathematical problem, an answer might be something like "colored graph".

  • Clearly one can not say everything; yet there are many questions which can be answered. For example, assume you want to know if it is likely that at some moment your population was divided in two and there were no interbreeding between these groups for a while. You can even estimate "time" when they split. BUT I'm interested in a more abstract way to describe the history --- I want to say something without any assumptions.

  • Something is possible: First note that with probability 1, there is one-to-one correspondence between humans and scars. Given scar $x$, let us denote by $H_x$ the corresponding human. Assume in the portion of population you have two humans: human $A$ who has scars $x < y$ and nothing in between $x$ and $y$ and human $B$ who has scars $x < z$ and nothing in between. Assume $z < y$ then $H_z$ is a descendant of $H_x$. That gives a partial order on all such humans. Is it all one can do?

share|cite|improve this question
The killing operation can be delayed until the end, so I'll ignore it. I'm not sure if this coordinate system helps to prove anything, but the possible humans can be identified with points in a simplicial complex with a natural coordinate system based on the possible choices of x. Each d-simplex corresponds to a human formed from recombining humans chosen in an a-simplex and b-simplex where a+b+1=d. I'm loosening the definition of simplicial complex so that a 3-cell can be attached to interpolate between two 1-cells (opposite edges of the tetrahedron) or at a point and 2-cell, for example. – Douglas Zare Jan 18 '10 at 12:34
@Douglas. "killing operation can be delayed until the end" --- nice observation (I thought about real live too much and did not see it). About your coordinate system --- I simply did not get it... Maybe you can start an answer and explain it? – Anton Petrunin Jan 19 '10 at 0:23
Edit 3 has removed most of the recombination description. I think it should say: $C = \lbrace x \rbrace \cup \lbrace a: a \lt x, a \in A \rbrace \cup \lbrace b: b \gt x, b \in B \rbrace$. – Hugo van der Sanden Jun 20 '10 at 9:21
@Hugo, it is corrected now – Anton Petrunin Jun 21 '10 at 8:20

This is not an answer, just an elaboration on the comment about associating a simplicial complex to the pattern of recombinations.

Recombination means if $A$ and $B$ recombine, the possibilities might be parametrized by $A \times B \times [0,1]$, although if the parameter is close to 0 or close to 1, almost no information is kept from one parent.

What geometric operation makes a child of parents $A$ and $B$ the structure $A \times B \times [0,1]$ with $A\times B \times \{0\}$ identified with $A$ and $A\times B \times \{1\}$ identified with $B$? The convex hull does that when $A$ and $B$ are in skew affine spaces. If $A$ and $B$ are simplices of dimensions $\alpha$ and $\beta$, that makes the child a simplex of dimension $\alpha+\beta+1$. If the points of $A$ are given barycentric coordinates, $(a_0,...,a_\alpha)$ with $\sum a_i = 1$ and similarly for $B$, then we can coordinatize the child as $((1-x)a_0,...,(1-x)a_\alpha,xb_0,...,xb_\beta)$. Inductively, we can specify a simplicial complex so that each person as a simplex, the initial population consists of points, and the recombination of two people is a person whose simplex is attached to the parent simplices at opposite facets.

The (point $p$ $\in$ simplex of person $P$) pairs correspond to choices of recombination points for $P$ and each ancestor of $P$. These choices may be inconsistent if there are multiple paths of descent from the same ancestor. Also, this doesn't fully take into account the way that recombination erases some of the information from each parent.

share|cite|improve this answer

I'm not sure what you mean by 'starts with a population formed by two empty sets'.

However, assuming you start with an initial population $P = \left\lbrace A_1, \ldots, A_n \right\rbrace$ where each individual $A_i = \left\lbrace a_{i1}, \ldots, a_{i{n_i}} \right\rbrace $.

Let $|A_i|$ be the complexity (number of genes?) of individual $A_i$, i.e. $|A_1| = |\left\lbrace a_11, a_12, a_13 \right\rbrace | = 3$, and $|P| = 1/n \sum_{i=1}^n |A_i|$ be the average complexity of all of the individuals in the population. Let $P'$ be this population after applying the 'killing' operation and $P''$ be this population after applying the 'recombination' operation. Then, after some basic algebra / logic, we see that

$E(|P'|) = |P|$ and $E(|P''|) = |P|$ too. Hence conversely, if $P_0$ was our initial population and $P_t$ is our population after $t$ applications of either the 'killing' operation or the 'recombination' operation, then

$E(|P_0|) = |P_t|$.

Not also that, as 'killing' removes one member of the population and 'recombination' adds one, we may model the total population as a random walk and so, for example, determine an expected initial population size based on current population and number of generations (off the top of my head it's also another invarient and so expected inital population = final population, although this needs checking.)

There are almost certainly other invarients.

On the more abstract side:

Call a population $P$ in which $\forall i,j$, $A_i \cap A_j = \emptyset$ pure.


  • Applying 'killing' to a pure population gives a pure population.
  • Applying 'killing' to a non-pure population MAY give a pure population.
  • Applying 'recombination' to a pure population gives a non-pure population.
  • Applying 'recombination' to a non-pure population gives a non-pure population.

As the probability of them being the same is 0, wlog we may assume all 'genes' of all individuals are unique - i.e. the inital population is pure. This gives us a 2 state system that models the population, passing between the pure and non-pure states by these 2 operations. As generations pass I would expect the population to become 'more non-pure' as the probability of the application of a killing operation reverting it to a pure population reduces. This should give us a method by which to determine an expected value for the number of itterations that have occured by measuring the 'purity' of the population.

share|cite|improve this answer
Recombination increases complexity on average. That's why you can start with two empty sets. – Douglas Zare Jan 18 '10 at 1:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.