Friday, May 30, 2008

King George

Over at Dispatches From The Culture Wars, Ed Brayton reports on a most disturbing case: a US resident who has been arrested in the US on suspicion of planning terrorist attacks, and is being held as an enemy combatant. The US government is arguing that they can hold him indefinitely.

In fact, they argue that they can do this to anyone in wartime; and that this is wartime:


The full appeals court is reviewing that decision and a ruling is expected soon. During arguments last year, government lawyers said the courts should give great deference to the president when the nation is at war.
"What you assert is the power of the military to seize a person in the United States, including an American citizen, on suspicion of being an enemy combatant?" Judge William B. Traxler asked.
"Yes, your honor," Justice Department lawyer Gregory Garre replied.


So apparently we've been at war since at least late 2001, and we still are. Who wants to guess when we would be declared "no longer at war"? And when was last time we weren't? There have been terrorist attacks on US targets many times (USS Cole, embassy bombings...) and we've had soldiers fighting or peacekeeping in other countries for a large fraction of the last century.

If this man is guilty, he should be tried and sentenced, and deported. If he's not guilty, he should be released. If they "know" he's guilty, and can't prove it... that's a risk that we as a society have chosen to take and woven into the fabric of our justice system. We have chosen not to lock people up who might be innocent, even though some of them are inevitably guilty.

I don't know if they can do this or not. I'm not a constitutional lawyer. But this sort of thing is the bedrock on which the US declared independence. Two of the complaints against the original King George were:

He has affected to render the Military independent of and superior to the Civil Power.
...depriving us in many cases, of the benefit of Trial by Jury:



One of Ed's commenters asks:

Just for the sake of argument (because I don't think anyone here will argue that the government's assertion is staggering), let's say that the Judicial branch rolls over on this issue. How could one then differentiate between the USA and a typical police state?


I have heard people call for George Bush's impeachment many times in the past few years, and I have always thought this hyperbole. Sure he's incompetent and destructive in his foreign and economic policy; but that's just my opinion, and the arguments rage. This changes my mind - this sort of attack on the very fabric of the United States cannot be ignored.

Everyone from Gregory Garre on up to whatever level approved this line of argument should be sacked immediately as not fit to hold public office. If that isn't the president, then the rest of the supervisory chain should be sacked for their manifest failure to oversee operations. This is not just one comment in a courtroom; this case has been going on since 2001.

It is not enough to defend society against terrorism; we must also keep a society worth defending. The United States threw out one King George; it does not need another.

Tuesday, May 27, 2008

Coding Haldane's Dilemma

// Here's the code; I've been lazy, so you have to change constants and
// recompile it to alter incremental fitness (INC)
//
// This code is public domain. Enjoy.

import java.util.Random;
import java.util.Arrays;
import java.util.Comparator;

class Substitute
{
/** How many critters to have **/
private static final int CRITTERS = 1024;
/** How many children per critter **/
private static final int CHILDREN = 2;
/** How many selectable traits to have **/
private static final int TRAITS = 20;
/** How many copies of gene in the DNA **/
private static final int COPIES = 2;
// Note that you can't just change COPIES and expect
// everything to work!
/** Rate of increase, must be less than CHILDREN **/
private static final double INC = 1.1;
/** How may trials to run **/
private static final int TRIALS = 100;

/** A random number generator for initial state **/
private Random mRand = new Random(System.currentTimeMillis());

/** How many generations have gone by **/
private int mGenerations = 0;

class Critter
{
/** No-args constructor **/
Critter()
{
for (int i = 0; i < TRAITS; i++)
{
mDNA[0][i] = mDNA[1][i] = false;
}
}
/** Constructor from two parents **/
Critter(Critter aP1, Critter aP2)
{
for (int i = 0; i < TRAITS; i++)
{
// Choose one chromosome randomly from each parent.
int c1 = mRand.nextInt(COPIES);
int c2 = mRand.nextInt(COPIES);
mDNA[0][i] = aP1.mDNA[c1][i];
mDNA[1][i] = aP2.mDNA[c2][i];
}
}

/** Give yourself a beneficial mutation **/
void setDNA(int aPos)
{
mDNA[0][aPos] = true;
}

/** Do you have this mutation? **/
boolean getDNA(int aPos)
{
return (mDNA[0][aPos] || mDNA[1][aPos]);
}

/** DNA of critter **/
private final boolean mDNA[][] =
new boolean[COPIES][TRAITS];
};

/** Sort version that has mutations strictly ordered **/
public static Comparator LOWEST_FIRST = new Comparator()
{
/** Compare two Critters **/
public int compare(Object aOne, Object aTwo)
{
Critter l1 = (Critter)aOne;
Critter l2 = (Critter)aTwo;
for (int i = 0; i < TRAITS; i++)
{
boolean mine = l1.mDNA[0][i] | l1.mDNA[1][i];
boolean theirs = l2.mDNA[0][i] | l2.mDNA[1][i];
if (mine != theirs)
{
// Smaller is better
return mine ? -1 : 1;
}
}
return 0;
}
/** Not using this, don't care **/
public boolean equals(Object aComp) { return false; }
};

/** Sort version that has mutations equivalent **/
public static Comparator ALL_SAME = new Comparator()
{
/** Compare two Critters **/
public int compare(Object aOne, Object aTwo)
{
Critter l1 = (Critter)aOne;
Critter l2 = (Critter)aTwo;
int total = 0;
for (int i = 0; i < TRAITS; i++)
{
boolean mine = l1.mDNA[0][i] | l1.mDNA[1][i];
boolean theirs = l2.mDNA[0][i] | l2.mDNA[1][i];
if (mine != theirs)
{
// Smaller is better
total += mine ? -1 : 1;
}
}
return total;
}
/** Not using this, don't care **/
public boolean equals(Object aComp) { return false; }
};

/** DNA of current generation **/
private final Critter mCurrent[] = new Critter[CRITTERS];
/** DNA of new generation **/
private final Critter mNext[] =
new Critter[CRITTERS * CHILDREN];

public Substitute()
{
// Create the critters
for (int i = 0; i < CRITTERS; i++)
{
mCurrent[i] = new Critter();
}
// One beneficial mutation in each trait to start;
// each one in a different critter.
for (int i = 0; i < TRAITS; i++)
{
mCurrent[i].setDNA(i);
}
}

public int getGenerations() { return mGenerations; }

public void nextGeneration()
{
int remains = CRITTERS;
int lWhere = 0;
for (int i = 0; i < CRITTERS / 2; i++)
{
// Choose two random current critters
Critter p1 = getRandom(mCurrent, remains--);
Critter p2 = getRandom(mCurrent, remains--);
// Reproduce them.
for (int j = 0; j < CHILDREN * 2; j++)
{
mNext[lWhere++] = new Critter(p1, p2);
}
}
// Kill off random children to simulate how
// difficult life is for everyone.
remains = CRITTERS * CHILDREN;
long target = Math.round(INC * CRITTERS);
while (remains > target)
{
getRandom(mNext, remains--);
}
// Pick out the genetically fittest.
// Change LOWEST_FIRST to ALL_SAME to give equal
// weight to all mutations
Arrays.sort(mNext, 0, remains, LOWEST_FIRST);
// And replace the current generation with the best
for (int i = 0; i < CRITTERS; i++)
{
mCurrent[i] = mNext[i];
}
mGenerations++;
}

/** Print stats and see if we should stop yet */
public boolean analyze()
{
boolean bStop = true;
for (int i = 0; i < TRAITS; i++)
{
int tc = 0;
for (int j = 0; j < CRITTERS; j++)
{
if (mCurrent[j].getDNA(i))
{
tc++;
}
}
if (tc < CRITTERS)
{
bStop = false;
}
if (tc == 0)
{
// Lost a mutation! Replacing...
int pos = mRand.nextInt(CRITTERS);
mCurrent[pos].setDNA(i);
}
}
return bStop;
}

/**
* Pick a random critter from the array, and
* shrink the array down so it's removed.
*/
private Critter getRandom(Critter[] aGroup, int aCount)
{
int c1 = mRand.nextInt(aCount);
Critter p1 = aGroup[c1];
aCount--;
aGroup[c1] = aGroup[aCount];
return p1;
}

/**
* Main method, contructs the scenario and sets it off
* @param aArgs any command line arguments (ignored at present)
**/
public static void main(String aArgs[])
{
int lMin = 100000;
int lMax = 0;
int lTotal = 0;

for (int i = 0; i < TRIALS; i++)
{
Substitute sub = new Substitute();
sub.analyze();
boolean bStop = false;
while (!bStop)
{
sub.nextGeneration();
bStop = sub.analyze();
}
int lGen = sub.getGenerations();
if (lGen < lMin) { lMin = lGen;}
if (lGen > lMax) { lMax = lGen;}
lTotal += lGen;
System.out.println("Completed run: " + i + " Result: " + lGen);
}
System.out.println("Min: " + lMin + " Max: " + lMax +
" Average: " + ((lTotal + TRIALS/2)/ TRIALS) +
" (Trials: " + TRIALS + ")");
}
}

Simulating Haldane's Dilemma

In my previous post, I calculated how long it would take for multiple beneficial mutations to substitute into a population, and showed that it happened much faster than substitution one at a time. What happens when you try this in a simulation?

Remine's web-page at http://saintpaulscience.com/Haldane.htm notes that "Cost arguments can apply to any evolutionary scenario, for any species, in any environment, and even including computer simulations." So results of a computer simulation (given the right assumptions) should be a valid test.

The simulation I set up worked like this: each individual has two sets of chromosomes. Each chromosome can either contain or not contain a beneficial mutation. At reproduction time, two individuals contribute one of each of their pairs of chromosomes (not necessarily all from the same set) to each child they have. The species is monogamous, so each parent mates with only one other parent, having a total of four children (2 per individual). The population starts with one of each mutation.

That would double the next generation's population, so some must be eliminated. First we kill off a randomly chosen set of individuals, to bring the numbers back to 1.1 per parent. This simulates accidents, harmful mutations, random predation, disease, and all the other things that interfere with selection. Now we take the best of the remaining individuals and make that the next generation.

Selection can be done in two ways. We can count the number of beneficial mutations each individual possesses, and sort by that. This assumes that each is about equal, and the more you have the better. Or we can sort "alphabetically" - that is, the first mutation rules unless both individuals have it; try the second if the first was even; then try the third, etc. This assumes that some mutations are better than others - the mutations do not interact especially favorably, but are still always advantageous.

The results of the simulation are naturally going to be variable; particularly in the early stages of a substitution, it's easy for a beneficial mutation to drift out when its numbers are small. The simulation assumes that beneficial mutations are available; if any vanish, they are replaced with a new single instance.

The result? I had a population size of 1024, so Remine and I would both agree that selecting one mutation takes about 80 generations (log2048 / log1.1 - it's 2048 because there are two copies of each gene). Where we differ is in how long it takes to substitute more. He would claim 80 generations for each extra substitution; I would claim only 11, and some of that to take place during the initial 80 generations.

With 1 mutation to substitute, 100 trials gave results anywhere between 53 and 192 generations, at an average of 86. That matches the prediction reasonably well (because of the random heritability, a mutation may leave anywhere from 0-4 copies, so sometimes a mutation will grow faster than expected or even shrink, particularly early in the run). With 5 mutations, Remine would predict 80 generations each - a total of 400. I would predict 80 for the first one, and less than 11 each for the rest (total of 124), as some of the substitution would be done in parallel.
Results of 100 trials: 92-243, at an average of 130.

With 20 traits, I predict 80 + 19 * 11 = 289; Remine predicts 1600.Results of 100 trials: 238-366, at an average of 279. Note that as larger numbers are involved, the results are more predictable.

Above I mentioned two different selection types; what happens if these are tried? The alphabetical approach means the first mutation always substitutes first, and so on in order. The counting approach means all the mutations end up substituting about the same time. But there is no significant difference in the overall approach (20 traits over 100 trials, 236-361, average 277).

Remine complains that low selection coefficients are generally assumed, which lowers the cost. So let's try 2 as the growth rate instead of 1.1:
1 Trait - both of us predict about 11 generations.
100 trials: 9-14, at an average of 11.
5 Traits - I predict about 11 + 4*2 = 19, Remine predicts 5*11 = 55
100 trials: 18-24, at an average of 20
20 Traits - I predict about 11 + 19*2 = 49, Remine predicts 20*11 = 220
100 trials: 54-65, at an average of 57

As you can see, Remine's expectations are not met.

Remine does make some valid points about the assumptions made; only some mutations will substitute this fast. But if you look at a genome, it will typically be dominated by the fast-substituting mutations, because more of them can substitute in a given time. Nor is it much of a surprise that the first species that's capable of figuring this out would come at the end of a burst of faster-than-average mutation; any new capability such as provided by human intelligence opens up a wide field of potentially beneficial mutation.

But the computer simulation confirms what the mathematics shows - the 300 generation speed-limit that Remine talks about is far slower than what is possible in reality. His argument fails to stand up, at least here.

This assumes truncation selection, which Remine doesn't like. So my next effort was to try individual selection, to see if that made a difference. Once again, this post is long enough already, so I'll leave that for another.

(Incidentally, if you're curious to see what the simulation looks like, I've added that in a separate post).

Friday, May 16, 2008

Haldane's Dilemma

Over at http://creationwiki.org/Haldane, Walter Remine has a page describing what he calls "Haldane's Dilemma". I recommend reading it; it's not some stupid quote-mine job, and Remine has thought hard about it. For one thing, he actually links to the original paper he's based this on (read that too!). And you can read his paper on cost theory at http://www.creationontheweb.com/images/journal_of_creation/vol19/costtheory.pdf to see that work has gone into this.

The essence of the idea is that there is a limit on how fast beneficial mutations can be substituted into the genome by natural selection, and that limit is too slow to add meaningful change to the human genome since the split from the chimp/human common ancestor.

A crucial part of this is that substituting multiple mutations at once does not speed this up; if one mutation takes n generations, 2 mutations takes 2n generations. This conclusion is far as I can tell based purely on Haldane's work, which again as far as I can tell comes down to this paragraph:

"Can this slowness be avoided by selecting several genes at a time? I doubt it, for the following reason. Consider clonally reproducing bacteria, in which a number of disadvantageous genes are present, kept in being by mutation, each with frequencies of the order of 10^-4. They become slightly advantageous through a change of environment or residual genotype. Among 10^12 bacteria there might be one which possessed three such mutants. But since the cost of selection is proportional to the negative logarithm of the initial frequency the mean cost of selecting its descendants would be the same as that of selection for the three mutants in series, though the process might be quicker. The same argument applies to mutants linked by an inversion. Once several favorable mutants are so linked the inversion may be quickly selected. But the rarity of inversions containing several rare and favorable mutants will leave the cost unaltered."

Many of you will have already spotted the key words here - "clonally reproducing". That means that if you don't have the beneficial allele in your DNA already, the only way your descendants will get it is by mutation. So although each mutation may be present at 10^-4, there is no way to combine them unless they randomly already are combined. The mutations must occur in a single line of descent.

But humans don't reproduce that way (in reality, neither do bacteria). Humans reproduce sexually, which allows beneficial mutations to spread individually and combine later. So how does this change Remine's numbers?

Essentially Remine's formula (and Haldane's) is that the minimum number of generations required for substitution is the log of the population size (in his paper he uses a population of 1,000,000) divided by the selection intensity (which can be roughly considered as the log of the maximum growth rate, and which Haldane estimates at 0.1 for typical species).

So, log (1,000,000) / 0.1 = 13.8 / 0.1 = 138 generations per mutation; Haldane considered that 300 generations would be a more typical figure. This represents a beneficial mutation starting out in one individual, and growing at the expense of the old-type genome, until it completely replaces it.

The beneficial mutation to be substituted will be found on one of the chromosomes in the genome. In a sexually reproducing species, you would expect the substitution to leave the variation in the other chromosomes untouched, as they would be thoroughly mixed by reproduction. Variation in the substituting chromosome would depend on the rate at which chromosomes recombine. If no other beneficial mutations were around, then the entire 138 generations would indeed be required for a single substitution.

What if there are other beneficial mutations, however? They would have considerable room to increase their own frequencies, just as the target mutation does. A mutation that grows exponentially from 1 to 1M will spend half its growth time at a frequency of less than 1 in 1000 - basically invisible to other mutations. So 1,000 other mutations might easily do half their substitution on other chromosomes, stay around unchanged as the second half of the substitution took place, and then fight it out to see who went next. Two substitutions in only 1.5 times the minimum for one.

Let's formalize this intuition by considering a population of constant size K, with a maximum growth rate for beneficial mutations of r (where selection intensity = log r). It would take n generations to substitute, where K = r^n (r is the nth root of K). So in generation i, there will be r^i individuals with a copy of the gene (completely removing all the old allele is roughly equivalent in cost to substituting into a population of 2K, which we'll ignore for now). And this will be the result of (r-1)r^i deaths of old-type individuals - and the extra births of the same number of new-type individuals.

So we expect that in each generation, (K-r^i) individuals don't have the new gene, but aren't killed off to substitute it, and are available as a population for the substitution of other genes. So our new gene is using up r^i/K of the species' ability to substitute new genes, in that generation.
Over the course of the entire substitution, it will use up 1/K(1 + r + r^2 + ... + r^n). Using the old compound interest formula, the total cost usage is then 1/K(r^(n+1) - 1)/(r - 1). Remembering that r^n = K, and assuming K >> 1, that simplifies to r/(r - 1), which for r = 1.1 means one substitution every 11 generations.

The limit described by Haldane is the latency, not the throughput. It will still take 138+ generations to subsitute a given mutation into a population of 1M. But others could start or finish during that time, using the leftover capacity described above.

Note that the throughput result, unlike the latency, is no longer dependent on the population size. A bigger population takes longer to subsitute individual mutations, but can be working on more things simultaneously (and actually has more capacity to generate benefical mutations). The only thing that matters is how much excess reproductive capacity the species has.

Sidenote: Remine spends most of a chapter of "The Biotic Message" wondering how evolution can explain the origin of sexual reproduction. Above we see that throughput of beneficial mutations is one every logK/logr generations for asexual species, and roughly one every 1/logr generations for sexual species. That is, sexual reproducers can adapt to new situations about logK times faster. This is *more* pronounced for large populations such as bacteria - and no wonder they still use sex, even if they don't tie it so directly to reproduction. Any multicellular species that failed to allow sex somewhere in its reproductive cycle would have been outcompeted by its rivals in a geological heartbeat.

How does this apply to humans? Remine claims that over the last 10M years, humans could have only substituted 500,000 / 300 = 1,667 mutations. The above shows that we are in fact capable of up to 500,000 / 11 = 45,454! And it's worth noting that the human race is currently doubling in size about every 50 years, even with very low birth rates in the developed world, and all the wars, famine, disease etc that we see. That would give a figure for r of 1.32 (assuming generations of 20 years), or one substitution every 4.125 generations. And that rate requires 2.64 children per family surviving to adulthood; clearly plausible.

The latest results from the human genome project (see http://www.ensembl.org/Homo_sapiens/index.html) show that humans have 21,541 genes. If we split from chimps 5M years ago - 250,000 generations - we've had time to substitute 60K mutations at 4.125 generations each. That is, almost three important mutations per gene; and that doesn't include neutral differences like multiple ways of coding for the same amino acid, or amino acid changes that don't affect protein function, all of which can piggyback on beneficial mutations. And that's just our side; the chimps have had time to do the same thing on theirs.

Calculations like the above are fine things, but experiment trumps theory. Fortunately, Remine notes that these limits also apply to computer simulations - so I don't need to keep a few hundred generations of cows at home to test my results. But this post is already way too long, so I'll leave that for another post.

Friday, May 09, 2008

I Find Your Lack Of Faith Disturbing

On the weekend the free-to-air TV was showing Revenge of the Sith, and I reflected on my previous comments about science and religion. The Jedi are one religious order who would not find themselves in conflict with science - they are able to display specific effects of their religion.

Jedi can jump higher, react quicker, and throw you across the room with mind power if they want. Sith can generate cool electric sparks from their fingers and choke you from a distance. Ignoring the ridiculous "midichlorians" that George Lucas came up with in The Phantom Menace, here's a religion that has nothing to fear from the march of science.

I mention this to contrast it with the religions that we have here in the real world. Where they make claims with real-world consequences (weeping statues, transubstantiation, creationism), they are invariably found to be false. Where they have no real-world consequences (the afterlife is the prime example), then science can have nothing to say about them; faith and religion are the only tools we can use.

Ignoring the inferences one draws about non-consequential beliefs from the failure of consequential ones, what the creationists are saying is that religion is a weaker tool than science; that faith is not enough. The more ground science covers without finding God, then, the better atheism will therefore look. The areas off-limits to science remain unchanged, but the creationist campaign will have cemented the idea that these areas are less important. I happen to agree with that, but I don't think they would.

But of course, if a religion were to make real-world claims that could be verifiable - if the Jedi were to turn up - then the picture would be substantially changed.

I see no prospect of that happening.

Friday, May 02, 2008

Framing

The Panda's Thumb reports a great essay by John Derbyshire on why creationists have become such slime-balls. Basically, they are trying to get creationism into the classrooms without admitting that it's religion; and the dishonesty of their main argument spills over into everything that they do.

But in the process, they are also giving atheists a huge propaganda victory. Aside from associating religion with dishonesty, I mean. There are are two prongs to the current strategy: first, that creationism is really science, not religion (this used to mean bizarre theories about vapor canopies, but now it means Intelligent Design); and second, that Darwinism is really religion, not science.

What do these prongs mean? Firstly, that a religious belief that becomes scientific is promoted; secondly, that a scientific theory thet becomes religious is demoted. The same thing, in both cases - science is better than religion.

Science is a far more effective way of knowing about the world than religion, because it eliminates personal biases, and authority figures, and herd mentalities, and all the errors that humans are prone to. Not perfectly, but better than anything else we've found.

And science has never found God; nor does it seem likely to. If it does, well, things will change - but if it does it will likely not be the God that mainstream religion talks about. And in the meantime, the creationists are reinforcing the idea that science is the right way to find out.