Roadmap: Graph Summarization

[josiahseaman]

Implement a method of summarizing the variation inside of a graph.

• Drop out small, uncorrelated variation as noise while preserving correlated variation and building them into haplotype blocks.
• Iterative process of summarization for different zoom levels
• Strategies for summarizing different types of structures are described in our Google Doc.

Prototype Progress

• Graph Summarization figures
• data representation prototype - collab with Toshiyuki?
• Summarization add sequence
• Summarization add penalties in paths
• Utility scoring
• Brains of Graph Summarization prototype - deterministic
• Chaining Split Vertical haplotype blocks

[josiahseaman]

My Goal for this week is adding sequence and sequence identity penalties into my summarization prototype.

[josiahseaman]

I've read "Distribution of recombination crossovers and the origin of haplotype blocks" (Wang et al. 2002) and "The structure of haplotype blocks in the human genome" (Gabriel 2002). The first paper points to the 4 Gamete Test for recombination points outlined in (Kaplan 1985). The approach appeals to me because it's very binary and easily implemented. We'd eventually want to upgrade to (Gabriel 2002) method. The 4 Gamete Test is clearly overly sensitive, however that's precisely what we'd want for the first level of summarization. Everything that can be easily dismissed gets dismissed first, leaving us with a pile of candidates we can devote compute power to telling if they're false positives / erroneous.

I'm currently working on a generalization of their approach to graph genomes with an arbitrary number of paths and arbitrary number of alternatives. I think it's possible to make a 5 gamete test, a 6 gamete test and so on that may serve as zoom layers. I'll keep working on it for now.

[josiahseaman]

May also be relevant:

From 2004 Paper: https://academic.oup.com/bioinformatics/article/21/2/263/186662

[josiahseaman]

Haploblocker

http://dx.doi.org/10.1534/genetics.119.302283
https://www.genetics.org/content/genetics/early/2019/05/31/genetics.119.302283.full.pdf

Haploblocker looks like they have a lot of reusable concepts and methods. Figure 2 (below) looks very similar to the graph summarization algorithm that I specced out and prototyped for graph genomes. The key unexpected similarity is that they use SNP data to build a graph with slices that represent all the variation. So from dissimilar data, they build essentially the same data structure as us. I think this would work on full sequences.

Figure 5 looks very similar to a glimpse of what I was proposing to do with sorting and aggregating Paths into Ribbons. Bernardo (Earlham) pointed out that a dendrogram of similar paths was necessarily local, not global. This figure is a great depiction of why. TubeMap gives us the option to gradually rearrange ordering as we go, so we could conceivable keep fragmentation in check. Though we need to represent that graphically if we're allowing paths to migrate from one ribbon color to another.

Computing Time

"with the full dataset 895 (501 haplotypes, 80,200 SNPs) needing 55 seconds on default, 75 896 seconds with a target coverage and 13.3 minutes in the adaptive 897 mode."
Our dataset is roughly 1,000 haplotypes and 150,000,000 bp 'SNPs' except that much of the sequence doesn't have any variance (99%), so we could likely cut it down by 100x. 1,500,000 * 1,000 = (1500000000 / (501 × 80200)) = 37x larger dataset. Meaning 37 minutes to 8 hours for our complete dataset. Those are still very reasonable times assuming this scales linearly. But the authors say the scaling is likely better than that: "The marker density only had a minor effect. Even a panel containing just every tenth marker, on average, needed 99.3% of the computing time of the full dataset."

They appear to agree on the applicability of the method to sequence.
"A future topic of research is the explicit inclusion of larger structural variation like duplications, insertions or deletions as is done in methods to generate a pangenome (Eggertsson et al. 2017). Since blocks in HaploBlocker are of large physical size most structural variation should still be modelled implicitly and an application to sequence data is perfectly possible."