Sunday, September 27, 2015

Visualize DNA matches graph

Through high-throughput SNP genotyping it has become possible to identify shared DNA with our fifth degree cousins. Two companies, 23andMe and AncestryDNA, currently each hold each a database of more than one million people of dense genotype data. Each database gives us the possibility to identify hundreds of distant DNA cousins as each service reports a list of all individuals who share DNA segments at least 5 centimorgans long.

DNA cousins from 1st up to 4th degree will usually share several such DNA segments making them stand out from the crowd of more distantly related DNA cousins. For the large list of individuals that only share with us one or two DNA segments, it is difficult to distinguish between a match as close as a fifth degree cousin and someone much more distantly related who just happens to share a long DNA segment which through luck stayed intact across several centuries.

Is there any information other than the number of shared DNA segments and their length in centimorgans that we can leverage to prioritize our DNA matches? Since August 26th 2015, AncestryDNA has launched a feature whereby for a given match we can further learn whether it in turn shares DNA with other of our DNA matches, with some limitations. We can also do the same for DNA matches that have agreed to share genomes with us on 23andMe, though it is a little bit more cumbersome.

We can therefore define a DNA matches graph where each node is one of our DNA matches and two nodes are connected by an edge if the two corresponding DNA matches share DNA with each other. What can we learn from this graph? What does the topology look like? Does the graph contain connected components? For example, if our parents were to be from very different places, it would be quite unlikely that our DNA matches from our mother's side would be connected to our DNA matches from our father's side. The same holds if our grandparents are from different places, and so on.

To be able to glance at our DNA matches graph, we need to access all the information that either AncestryDNA or 23andMe provides us at once. To retrieve this information manually is just impractical. To overcome this hurdle, I have put together a few python scripts which will do the job for us.

The workflow runs as follows:
1) We dump all DNA matches information in our user account
2) We process the information to generate a table of all pairwise DNA sharing
3) We visualize the DNA matches graph

However, for now, you will have to be familiar with running python commands and installing a few necessary python packages. Here are some examples of what came out for my mother's 23andMe test:

The blue nodes correspond to DNA matches on my paternal grandmother's side and the pink nodes correspond to DNA matches on my maternal grandmother's side. Interestingly these two groups form two very separate clusters and this is to be expected as my maternal grandparents come from two Italian towns quite distant from each other.

The following example is from the AncestryDNA account of an American friend of mine:

The small nodes correspond to DNA matches estimated as my friend's distant cousins, while the larger nodes are estimated as 4th cousins or closer, and the dark colored nodes correspond to nodes for which AncestryDNA has identified the most recent common ancestor in the family trees within nine generations. The clusters make some sense. For example, we were able to identify a little one corresponding to a little town from Poland where my friend's great-great grandmother is from. It is a great graph and I am jealous because if you have Northern European roots, you get a lot more DNA matches than if you have Southern European roots like me, most likely due to the bias in which individuals buy the AncestryDNA test.

If you are savvy enough, I encourage you to use the tool on your own data and do send me feedback! :-)

Limitations of 23andMe and AncestryDNA

When taking a DNA test with 23andMe or AncestryDNA all matches sharing at least 5 centimorgans with the individual being tested will be reported for further review. In either case some matches will be anonymous and some matches will share as much as their own family tree, depending on the settings selected by the user. I believe for chromosome X matches for males 23andMe might be lowering the threshold to something like 2 centimorgans as it is significantly easier to identify sharing on the X chromosome among males. This 5 centimorgans threshold for shared segments is likely selected for two reasons:

1) Shorter segments become increasingly likely to be false positives below 5 centimorgans without your genome being properly phased which is mostly not the case with the exception of those customers who also had their parents tested.

2) Shorter segments are likely to be due to really far away relationships and as such they might have very little value for genealogy as they would trace back several centuries, much beyond what the paper trail allows in most countries.

Limitations of 23andMe

When browsing the Relative Finder feature within 23andMe, you can see a full list of individuals sharing with you DNA segments larger than 5 centimorgans. For each DNA match you can also see how many separate segments you share, unlike AncestryDNA. However, you cannot determine whether two of your DNA matches are DNA matches with each other unless both users have agreed to share their genetic profiles with you.

Due to this limitation you can only build the DNA matches graph for a restricted class of individuals who are engaged enough in the service to be able to manage their sharing requests. Furthermore, you can only retrieve information for one pair of individuals at a time, making the process completely impractical if attempted manually. Due to how slow the 23andMe server is at retrieving such information, even with the script mentioned above, it will take about three seconds to retrieve information about each pair. For 250 individuals it might take approximately 24 hours, even if most retrieval requests will yield empty results.

Limitations of AncestryDNA

Unlike 23andMe, AncestryDNA does not report the number of shared segments among DNA matches nor the amount of genome shared. However, when browsing the site the browser does receive two variables invisible to the user:

1) sharedCentimorgans being an estimate of the amount of DNA shared across shared DNA segments larger than 5 centimorgans

2) meiosisValue being an estimate from sharedCentimorgans of the number of meioses separating you and your DNA match and this number is never larger than 10

From what I observed pairs of individuals within the AncestryDNA database can then be split in three categories:

1) Pairs that share no DNA segments larger than 5 centimorgans

2) Pairs that share at least one DNA segment longer than 5 centimorgans with a meiosisValue of exactly 10 (corresponding to sharedCentimorgans between 5 and 17.65, that is, relationships classified as 10:DISTANT COUSIN)

3) Pairs that share at least one DNA segment longer than 5 centimorgans with a meiosisValue smaller than 10 (corresponding to sharedCentimorgans greater than 17.65, that is, relationships classified as 0:SELF/TWIN, 1:PARENT/CHILD, 2:IMMEDIATE FAMILY, 3:CLOSE FAMILY, 4:1ST COUSIN, 5,6:2ND COUSIN, 7:3RD COUSIN, 8,9:4TH COUSIN)

When accessing your AncestryDNA test, you will have reported all DNA matches corresponding to the last two categories. Most (in my case 96-98%) of your pairs including you and one of your DNA matches will fall in the second category. However, when you are reviewing one of your DNA matches A in AncestryDNA, the Shared Matches feature will list only DNA matches B such that both A and B and you and B fall in the third category as also explained in another post.

As of this writing, even when listing the DNA matches you have in common with your father/mother you are actually only listing those DNA matches which make a third category pair with your father/mother. Such limitation is not present with 23andMe but I believe this is just a bug on AncestryDNA's side which will get fixed soon.

To summarize, through AncestryDNA you will only have access to those edges of the DNA matches graph corresponding to pairs sharing at least 17.65 centimorgans of DNA. This is quite a conservative selection and likely the result of careful debate within AncestryDNA to find a balance between being at the same time informative and concise.