Tuesday, July 6, 2010

Combinatorial Principles for DNA Sharing, 1 of 7

This is the first in a series of 7 posts on sharing combinatorics:

Part 1: Combinatorial Principles for DNA Sharing

Part 2: Non-transitivity

Part 3: A Genetic Pigeonhole Principle

Part 4: Transitivity Principles

Part 5: X-Chromosome Transitivity Principles

Part 6: Mutual Sharing Principle

Part 7: Exceptions

 

This series of posts is about several combinatorial principles that apply to DNA sharing among three or more people.

For a brief introduction to sharing and half-identical regions, please see Basics: Sharing and Half-Identical Regions.
 

Sharing isn't transitive. You can find instances on 23andMe where somebody shares on the same region with two different people, but those two people don't share with one another.

So, if Alice shares with both Bob and Charlie (on the same region), we can't infer that Bob and Charlie must share. But what if Alice also shares with a third person on the same region—Bob, Charlie, and Deborah? Can we reach any conclusion about Bob, Charlie, and Deborah?

Here's another way to look at this: If Alice shares with Bob and Bob shares with Charlie (on the same region), we can't conclude that Alice shares with Charlie. But what if Alice shares with two people, both of whom share with Charlie? Or three people? Or five people?

Or, what if we just have a number of people, all of whom share with one another on the same region? Can anything be concluded from that?

It turns out that there are some combinatorial principles that apply to sharing, even though simple transitivity fails to hold.

No comments:

Post a Comment