Gene incongruence: which loci have a different history from the rest

Ask which loci of a multi-locus alignment have a different history from the rest: for each locus, how many extra parsimony steps it costs to force it onto the same tree as the others, and whether that cost is more than random deals of the same columns would give, with the false discovery rate controlled across loci.

What it doesCopy Anchor Link

Choose two or more files, one aligned locus each, whose records name the same taxa; records are matched across files by name. The test runs once over every locus together and once for each locus against the others concatenated. The result gives the length of the combined data on its best tree, each locus's own length and the rest's, the extra steps one shared tree costs, the same quantity under random deals of the columns, and a p-value and q-value per locus. A run is thousands of tree searches, so it runs in the background with a count of the searches done, and can be stopped.

When you’d use thisCopy Anchor Link

• Before concatenating genes into one tree. A locus whose tree conflicts with the others will pull a concatenated tree towards its own history.
• Finding candidate recombinant or transferred genes in a multi-locus scheme, to compare their trees by eye or with a likelihood test.
• Checking a bacterial typing scheme for loci that do not share the clonal history.

What this computesCopy Anchor Link

• L(all): the parsimony length of the concatenated loci, under unweighted Fitch parsimony with every character state counted, a gap as a fifth state
• L of each locus on its own tree, and L of the rest, the other loci concatenated
• D, the incongruence length difference of Farris, Källersjö, Kluge and Bult: L(all) − Σ L(parts), for the global test over every locus and for each locus against the rest
• the null distribution of D, from random deals of the same columns into parts of the same sizes, and its mean
• the Monte Carlo p-value, (1 + deals with D at or above the observed) / (deals + 1), with a 95% Clopper–Pearson interval on the fraction of deals at or beyond D
• the q-value of each locus, by Benjamini–Hochberg (independent or positively dependent tests) or Benjamini–Yekutieli (any dependence, less power), and the loci called at the false discovery rate you set

Each length is a hill-climb by nearest-neighbour interchange from the neighbour-joining tree of that alignment's p-distances, rooted at its midpoint, for the observed loci and every deal alike. Each deal draws from its own seeded random stream, so a run is reproducible and one deal can be re-run alone.

Every result states, in words generated from the run, which loci were called and by how much, why a called locus is a candidate rather than a recombination call, how many tests sat at the smallest p the number of deals allows, whether the global test and the per-locus tests disagree, and any test whose D came out below zero because a search stopped at a local optimum.

Worked exampleCopy Anchor Link

The seven Neisseria MLST loci (abcZ, adk, aroE, fumC, gdh, pdhC, pgm, 3,284 columns) of the 16 lowest-numbered founder sequence types of PubMLST's clonal complexes, 99 deals, Benjamini–Hochberg at q ≤ 0.05:

• All seven loci together cost 836 steps. One shared tree costs 333 steps more than seven separate trees, against a mean of 35.6 over the deals (p = 0.01, the smallest 99 deals allow).
• Every locus is called against the rest: pdhC by 107 extra steps (4.5 by chance), aroE 98, pgm 83, abcZ 70, gdh 49, fumC 31 and adk 27, each at q = 0.01.

Neisseria housekeeping genes recombine often, so a strong signal is expected. A control shows the test is not simply rejecting everything here: split each locus into two halves by alternate codons, which share one history, and none of the seven rejects (p from 0.45 to 1). Split each into its 5′ and 3′ halves instead and aroE, gdh and pdhC reject: contiguous halves of a mosaic allele can have two histories.

On all 62 founder sequence types the answer holds and sharpens: one shared tree costs 1,715 steps more than seven separate trees against 190 by chance, and every locus is called, aroE most (589 extra steps against 37) and adk least (117 against 40). The interleaved-codon control still rejects at none of the seven loci (p 0.08 to 0.96). At 99 deals this run took 87 minutes, measured outside the browser.

LimitationsCopy Anchor Link

• A called locus is not a recombination call. The test also rejects loci that evolve at different rates or with different rate variation among sites (Darlu and Lecointre 2002).
• Lengths are heuristic. A nearest-neighbour search can stop at a local optimum, which overstates a length; the same search is used for the observed loci and every deal, which keeps the comparison fair but does not make each length the shortest possible.
• The smallest p is 1 / (deals + 1). With 99 deals every strong conflict reads 0.01, and the q-values cannot fall below it. Raise the number of deals to rank strong conflicts.
• Cost grows quickly with taxa. The 16-strain example takes under a minute; 62 strains of the same seven loci took 87 minutes at 99 deals, measured outside the browser.
• Loci must already be aligned, and every file must name the same taxa.

Where the numbers come fromCopy Anchor Link

Every parsimony length a run computes, for the observed loci, the rest of each locus, and every deal of a three-deal run on 12 strains of the same corpus, is checked against Bio.Phylo's own nearest-neighbour parsimony search started from the same tree. The false discovery rate is checked against R's p.adjust.

AutomationCopy Anchor Link

The same test is a workflow node and a tool the assistant can call, with the same settings and defaults as the panel; each locus is the name of an aligned FASTA file.