Epigenomes and intervals | Databio Slides

# Epigenomes and intervals

Nathan Sheffield

<span style="font-size:0.6em"><a href="http://www.databio.org/slides">www.databio.org/slides</a></span>

</section>
---

# Mission statement

We develop and apply computational methods<br/>
to organize, analyze, and understand large epigenomic data.<br/><br/>
<img src="/_modules/mission-statement/understand.svg" width="695">
<br> <img src="/_modules/mission-statement/logo_databio.svg" width="195">
</section>
---

# Full-stack bioinformatics

</section>

---

# Biological motivation

<div class="col2">
<br><br>
<img src="/_modules/bio-motivation-regulatory-dna/dna_folding_diversity.svg" width="400"><br/>
Cells alter phenotype by using DNA differently. <br>
</div>

<div class="col2 fragment">
<img src="/_modules/bio-motivation-regulatory-dna/differentation_gone_awry.svg" width="500"><br/>
Breakdowns lead to disease
</div>
---

## What is epigenetics?

---

<div class="well">
There has always been a place in biology for words that have different meanings for different people. Epigenetics is an extreme case, because it has several meanings with independent roots. (Bird 2007)
</div>

<div class="well">
The meaning of the term "epigenetics" has itself undergone an evolution. (Felsenfeld 2014)
</div>

---

<div class="well">
the causal study of embryological development (Waddington 1957, The strategy of the genes)
</div>

---

---

<div class="well">
The study of mitotically and/or meiotically heritable changes in gene function that cannot be explained by changes in DNA sequence (Riggs et al. 1996)
</div>

---

<div class="well">
a change in the state of expression of a gene that does not involve a mutation, but that is nevertheless inherited in the absence of the signal (or event) that initiated the change. (Ptashne and Gant 2002)
</div>

---

<div class="well">
the structural adaptation of chromosomal regions so as to register, signal or perpetuate altered activity states. (Bird 2007)
</div>

---

## What is epigenetics?

<div class="well">
the causal study of embryological development (Waddington 1957, The strategy of the genes)
</div>

<div class="well">
The study of mitotically and/or meiotically heritable changes in gene function that cannot be explained by changes in DNA sequence (Riggs et al. 1996)
</div>

<div class="well">
the structural adaptation of chromosomal regions so as to register, signal or perpetuate altered activity states. (Bird 2007)
</div>

---

## What is epigenetics?

<div class="well">
Epigenetics refers to changes in gene regulation brought about through modifications to the DNA's packaging proteins or the DNA molecules themselves without changing the underlying sequence. (Lord and Cruchaga 2014, Nature Neuroscience)
</div>

<div class="well">
the study of the mechanisms that allow cells to translate the nearly constant genome content of a multicellular organism into multiple functional and stable cellular conditions (Schwartzman and Tanay 2015)
</div>

<div class="well">
Epigenetic processes are a means by which endogenous and exogenous cues exert long-term control over gene expression (Nugent et al. 2015)
</div>

---

## What is epigenetics?

The pop definition:

<div class="well">
The word literally means "on top of genetics," and it's the study of how individual genes can be activated or deactivated by life experiences. (<i>The Week</i>, 2013)
</div>

---

---

---

---

## What is epigenomics?

<div class="well">
epigenomics is the study of the physical modifications, associations and conformations of genomic DNA sequences (Schwartzman and Tanay 2015)
</div>

<div class="well">
epigenomics is the study of the chemical modification and physical conformation of cellular DNA and bound proteins (Sheffield 2017)
</div>

<i>The word "epigenome" lacks the baggage of heritability.</i>

---

Rosa et al. 2013

---

## Histone variants

https://en.wikipedia.org/wiki/Histone_octamer

---

## Histone modification (PTM)

https://en.wikipedia.org/wiki/Histone

---

## DNA Methylation

---

## Chromatin conformation

<img src="/_modules/epigenetics/chromatin-conformation.png" width="900">
---

Genomic intervals

---

![intervals](/_modules/intro-to-genomic-intervals/intervals.svg)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks

---

## Peaks

![peaks](/_modules/intro-to-genomic-intervals/peaks.svg)

Genomic intervals are often colloquially referred to as 'peaks'.

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)

---

## SNPs

SNPs are interval of width 1

![snps](/_modules/intro-to-genomic-intervals/snps.svg)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)
- Genes and gene components (TSS, exons, introns, etc)

---

## Genes and gene components

![brca2 gene model](/_modules/intro-to-genomic-intervals/brca2-gene-model.png)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)
- Genes and gene components (TSS, exons, introns, etc)
- Non-coding DNA annotation (promoters, enhancers)

---

## Non-coding DNA annotation

![regulatory build](/_modules/intro-to-genomic-intervals/regulatory-build.png)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)
- Genes and gene components (TSS, exons, introns, etc)
- Non-coding DNA annotation (promoters, enhancers)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)
- Genes and gene components (TSS, exons, introns, etc)
- Non-coding DNA annotation (promoters, enhancers)
- Protein domains

---

## Protein domains

![ets domains](/_modules/intro-to-genomic-intervals/ets-domains.jpeg)

---

## What can be represented as an interval?

- ChIP-seq or ATAC-seq peaks
- Single-Nucleotide Polymorphisms (SNPs)
- Genes and gene components (TSS, exons, introns, etc)
- Non-coding DNA annotation (promoters, enhancers)
- Protein domains
- Anything else?

---

# Key point

<span class="fragment">
Because of the linear nature of DNA and RNA, many biological entities can be conceptualized as genomic intervals.
</span>
<span class="fragment">Genomic intervals are often a simplified abstraction of genomic sequence.</span>

<span class="fragment">
Interval operations are fundamental in genomics
</span>
---

### Locus Overlap Analysis

<div class="small">
<a href="http://code.databio.org/LOLA/">http://code.databio.org/LOLA/</a><br>
</div>
<span class="small bullet"><img src="/_modules/lola-intro/paper.svg" height="25" class="bullet">Sheffield and Bock (2016). <i>Bioinformatics</i>.</span><br/>
<span class="small bullet"><img src="/_modules/lola-intro/paper.svg" height="25" class="bullet">Nagraj, Magee, and Sheffield (2018). <i>Nucleic Acids Research</i>.</span>
---

<div class="small">
<a href="http://code.databio.org/LOLA/">http://code.databio.org/LOLA/</a><br>
</div>

<span style="font-size: 0.8em;"><img src="/shorts/lola/paper.svg" height="25" style="vertical-align: text-bottom; margin-right: 5px;">Sheffield and Bock (2016). *Bioinformatics*.</span><br/>
<span style="font-size: 0.8em;"><img src="/shorts/lola/paper.svg" height="25" style="vertical-align: text-bottom; margin-right: 5px;">Nagraj, Magee, and Sheffield (2018). *Nucleic Acids Research*.</span>

---

![New data](/shorts/lola/01-new-data.svg)

---

![New data connection](/shorts/lola/02-new-data-connection.svg)

---

![GSEA](/shorts/lola/03-gsea.svg)

---

![HTS](/shorts/lola/04-hts.svg)

---

![Convert](/shorts/lola/05-convert.svg)

---

![Introducing LOLA](/shorts/lola/06-introducing-lola.svg)

---

![LOLA 1](/shorts/lola/07-lola1.svg)

---

![LOLA 2](/shorts/lola/08-lola2.svg)

---

![Test](/shorts/lola/09-test.svg)

---

![Results](/shorts/lola/10-results.svg)

---

![EWS vs others 2](/shorts/lola/ews_vs_others2.svg)

---

![EWS vs others 3](/shorts/lola/ews_vs_others3.svg)

---

## LOLAweb

A shiny app and server for interactive LOLA analysis.

Public server: [http://lolaweb.databio.org](http://lolaweb.databio.org)

GitHub: [https://github.com/databio/LOLAweb](https://github.com/databio/LOLAweb)

---

### DEMO

<video controls width="800">
  <source src="lw.webm" type="video/webm">
Your browser does not support the video tag.
</video>
---

### Augmented Interval List (AIList)

A novel data structure for efficiently computing overlaps <br>
across genomic interval data.<br>

<div class="small">
<a href="http://ailist.databio.org/">http://ailist.databio.org/</a><br>
</div>

<span class="small bullet"><img src="/_modules/ailist/icons/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1093/bioinformatics/btz407">Feng et al. (2020). <i>Bioinformatics</i>.</a></span>
<br>
<div style="padding:12px; font-size: 16pt; display:inline-block;">
<span style="border: 0px solid grey; float:right; margin: 0px 4px; padding: 0px 4px">
<img src="/_modules/ailist/Feng.jpg" width="100" style="margin:0px;">
<br>Jianglin Feng
</span>
</div>
---

# LOLA refresher

![LOLA abstract](/shorts/ailist/lola-abstract.svg)

---

# LOLA requires comparing sets of intervals

![Subject query](/shorts/ailist/subject-query.svg)

Can we improve the efficiency to enable faster, larger-scale analysis?

---

# If subject list has no containment, identifying overlaps is fast

![Subject query annotated](/shorts/ailist/subject-query-annotated.svg)

binary search on start intervals, followed by backward steps:

![Binary search](/shorts/ailist/binary-search.svg)

---

# The problem arises with contained interval overlaps

![Subject query containment](/shorts/ailist/subject-query-containment.svg)

![Binary search fail](/shorts/ailist/binary-search-fail.svg)

---

# How can we improve efficiency without guaranteeing no containment?

---

# Many approaches to solve the 'containment' issue:

- Nested Containment Lists (GRanges) (Alekseyenko and Lee, 2007; Aboyoun, P, Pages, H, and Lawrence, 2012)
- R-trees (bedtools) (Kent et al., 2002; Quinlan and Hall, 2010), Augmented interval trees (Cormen et al., 2001)

These methods try to structure the data to provide non-containment guarantees

---

# Methods provide non-containment guarantees

### R-trees

Annotates tree nodes with a *minimum bounding rectangle* of elements. A query that does not intersect the bounding rectangle will not intersect any child element.

</div>

### Nested Containment Lists

![NCList](/shorts/ailist/nclist.png)

</div>

---

# Augmented Interval List

1. Augment the list with the running maximum *end* value. *solves the problem for lowly-contained lists*

2. Decompose the list to minimize containment. *extends the solution to highly-contained lists*

---

# Augment with the running maximum end value, `maxE`

Provides a *local guarantee* of no containment.

![AIList maxE](/shorts/ailist/ailist-maxE.svg)

---

# AIList works on contained lists

![Subject query containment](/shorts/ailist/subject-query-containment.svg)

![Binary search maxE](/shorts/ailist/binary-search-maxE.svg)

---

# But long containment runs are problematic

![Subject query containment2](/shorts/ailist/subject-query-containment2.svg)

![Binary search maxE2](/shorts/ailist/binary-search-maxE2.svg)

---

# Decompose long runs with constant `maxE`

![AIList decompose](/shorts/ailist/ailist-decompose.svg)

---

# Performance

- How does the `maxE` minimum run length affect performance?
- How does it compare to existing approaches?
- How does it scale with increasing size of subject?

---

# Datasets

![Table 1](/shorts/ailist/ailist_table1.svg)

---

# How does the `maxE` minimum run length affect performance?

![Figure 2](/shorts/ailist/ailist_fig2.svg)

---

# How does it compare to existing approaches?

![Figure 3](/shorts/ailist/ailist_fig3.svg)

---

# How does it scale with increasing size of subject?

![Figure 4](/shorts/ailist/ailist_fig4.svg)

---

# Conclusion and Directions

AIList is best-in-class for one-to-one interval comparisons

---

## Acknowledgments

**Sheffield lab**
- John Lawson
- Vince Reuter
- Ognen Duzlevski
- Jason Smith
- **Jianglin Feng**
- Michal Stolarczyk
- Aaron Gu
- Anant Tewari

</div>

**Funding:**

</div>

</div>
---

### Region-set 2 Vec

Embeddings of genomic region sets <br> in lower dimensions.

<div class="small">
<a href="https://github.com/databio/regionset-embedding">https://github.com/databio/regionset-embedding</a><br>
</div>

<span class="small bullet"><img src="/_modules/regionset2vec/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1093/bioinformatics/btab439">Gharavi et al. (2021). <i>Bioinformatics</i>.</a></span>
<br>

<div style="padding:12px; font-size: 16pt; display:inline-block;">
<span style="border: 0px solid grey; float:right; margin: 0px 4px; padding: 0px 4px">
<img src="/_modules/regionset2vec-extension/Erfaneh.jpg" width="100" style="margin:0px;">
<br>Erfaneh Gharavi
</span>
</div>
---

<div>
<h3>Region-set 2 Vec</h3>

Embeddings of genomic region sets <br> in lower dimensions.

<div class="small">
<a href="https://github.com/databio/regionset-embedding">https://github.com/databio/regionset-embedding</a><br>
</div>
</div>
<span class="small bullet"><img src="/_modules/regionset2vec/paper.svg" height="25" class="bullet"><a href="https://doi.org/10.1093/bioinformatics/btab439">Gharavi et al. (2021). <i>Bioinformatics</i>.</a></span>

---

### Word embeddings

<div class="small">http://suriyadeepan.github.io</div>

---

### Word2vec model

<img src="/_modules/regionset2vec/mikolov2013_fig1.png" width="680">
<br><span class="small bullet"><img src="/_modules/regionset2vec/paper.svg" height="25" class="bullet"><a href="https://arxiv.org/abs/1301.3781">Mikolov et al. (2013). <i>arXiv:1301.3781v3</i>.</a></span>

---

### Word context

<div class="well">
	You shall know a word by the company it keeps. (Firth 1957)<br>
	Words that occur in similar contexts tend to have similar meanings.
</div>
<div class="small">Image credit: Shubham Agarwal</div>

---

### Genomic context

<div class="well">
	A genomic interval is more likely to appear in a BED file with other genomic intervals of a similar function.
</div>

---

---

### Genomic Interval Embeddings

---

### Evaluation

We have created unsupervised 100-dimensional vector representations (embeddings) of region sets.<br>
Do relationships among vectors reflect biology?

---

## Evaluation 1: Classification performance

---

## Evaluation 1: Classification performance

---

### Evaluation 1: Classification performance

---

### Conclusion

<ul>
	<li>Regionset2vec adapts word2vec to learn genomic region embeddings</li>
	<li>Regionset2vec embeddings capture biological information</li>
	<li>NLP approaches can be adapted for applications in genomic interval analysis</li>
</ul>
---

## Acknowledgments

**Collaborators**
<br>Vince Reuter
<br>Andre Rendeiro
<br>Levi Waldron

<br><br>
**Alumni**
<br>Aaron Gu
<br>Jianglin Feng
<br>Ognen Duzlevski
<br>Tessa Danehy
</div>

**Sheffield lab**
<br>Erfaneh Gharavi
<br>Michal Stolarczyk
<br>John Lawson
<br>Jason Smith
<br>Kristyna Kupkova
<br>John Stubbs
<br>Bingjie Xue
<br>Jose Verdezoto
<br>Nathan LeRoy
<br>Oleksandr Khoroshevskyi
</div>

<div class="col3" style="font-size:.6em">
<b>Funding:</b><br>
<br><img src="/_modules/ack-generic/University_of_Virginia_Rotunda_logo.svg" height="40"><img src="/_modules/ack-generic/University_of_Virginia_logo_white.svg" height="40">
<br><img src="/_modules/ack-generic/NIH_logo_black.svg" height="80"><br>NIGMS R35-GM128636
</div>
---

# Thank You

<span class="small bullet"><img src="/images/external/github_bug_black.svg" height="20" class="bullet"><a href="http://github.com/nsheff">nsheff</a></span> &middot;
<span class="small bullet"><img src="/images/icons/web.svg" height="25" class="bullet"><a href="http://databio.org">databio.org</a></span> &middot;
<span class="small bullet"><img src="/images/icons/letter.svg" height="25" class="bullet"><a href="mailto:nsheffield@virginia.edu">nsheffield@virginia.edu</a></span>

</section>