A New Model of Multi-Marker
Correlation for Genome-Wide Tag
SNP Selection
Wei-Bung Wang
Tao Jiang

Introduction

Outline{ Introduction{ Problem{ Related Work{ Our Approach{ Result1

Introduction

Single Nucleotide Polymorphism{ Single Nucleotide Polymorphism(SNP)

z A genetic variation

94%

CTTAGCTT

6%

CTTAGTTT
SNP
Modified from slide by Yao-Ting Huang,

National Taiwan University
Department of Computer Scienceand Information Engineering

Introduction

SNPs{ SNPs are usually bi-allelicz Major allele

94%

CTTAGCTTz Minor allele

6%

CTTAGTTT
SNP{ Minor allele frequency > 1% (or 5%){ Tri-allelic: very rare2

Introduction

Haplotype

TC-A C T T A G C T T-

Haplotype 1 C
Haplotype 2 CA

T-A A T T T G C T C-

Haplotype 3 A

TC-A C T T T G C T C-

SNP1 SNP2

SNP3

SNP1 SNP2 SNP3

Modified from slide by Yao-Ting Huang,

National Taiwan University
Department of Computer Scienceand Information Engineering

Introduction

Tag SNP{ What is a tag SNP?
{ Here I use some slides by Yao-TingHuang and Kun-Mao Chao

3National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPs
Haplotype patterns
S1S2S3S4S5
SNP S6loci S7S8S9S10S11S12An unknown haplotype sample

P1 P2 P3 P4Suppose we wish to distinguish
an unknown haplotype sample.
 We can genotype all SNPs toidentify the haplotype sample.
: Major allele: Minor allele

National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPs
Haplotype pattern
S1S2S3S4S5
SNP S6loci S7S8S9S10S11S12

P1 P2 P3 P4

In fact, it is not necessary togenotype all SNPs.
 SNPs S3, S4, and S5 can form
a set of tag SNPs.
P1 P2 P3 P4
S3S4S54

National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Wrong Tag SNPs
Haplotype pattern
S1
S2
S3S4
S5
SNP S6loci S7S8S9S10
S11S12P1 P2 P3 P4

SNPs S1, S2, and S3 can notform a set of tag SNPs
because P1 and P4 will beambiguous.

S1S2S3P1 P2 P3 P4National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPsHaplotype pattern
S1S2S3S4S5
SNP S6loci S7S8S9S10S11S12

P1 P2 P3 P4

SNPs S1 and S12 can form aset of tag SNPs.
 This set of SNPs is theminimum solution in thisexample.
S1

P1 P2 P3 P4

S125

Problem

Problem{ Tag SNP selectionz How to select representatives?
z Many different ways

Flowchart
A group of individuals(all SNPs are known)
SelectA set of SNPs
(tag SNPs)

?

Assay
Save money
here

What we doRelationships
between tag SNPs
and other SNPs

Haplotype:tag SNPs

Haplotype:all SNPs

6

ProblemProblem{ Perfect worldz Minimum set of tag SNPsz Save most moneyz NP-hard{ Real lifez Relatively small set
z Sufficient accuracy/confidence

A very frequently usedmethod is Linkage
A group of individuals
Disequilibrium(LD)(all SNPs are known)
SelectA set of SNPs
(tag SNPs)

?

Assay
Save money
here

What we do

Relationships
between tag SNPs
and other SNPs

Haplotype:tag SNPs

Haplotype:all SNPs

7

Related Work

Linkage Disequilibrium (LD){ Non-random association of alleles at

two or more loci

{ Correlated coefficient: estimation ofdependency{ LD = correlated coefficient =r2

Related Work

Linkage Disequilibriumr2 ={ r2(PA B ¡ PA PB ) 2PA Pa PB Pb

2 [0; 1]

{ r2 = 1: perfect correlation (A ,B ; a , b)r 2 = 1 , PA B = PA = PB
{ r2 = 0.9: strong correlation (0.95, etc.){ r2 = 0: no correlation

8

Related Work

An Example
Individ
SNP1 SNP2 SNP3 SNP4 SNP5 SNP6ual1AGACGT2TGCCGC3AA
ATAT4TGCTAC5TACCGCATACTC

Related Work

Minimum Dominating Set ProblemHighlycorrelated

SNP9National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPs
Haplotype patterns
S1
S2
S3
S4
S5
SNP S6loci S7
S8
S9S10
S11
S12

An unknown haplotype sample

P1 P2 P3 P4Suppose we wish to distinguish
an unknown haplotype sample.

: Major allele: Minor allele

National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPs
Haplotype patterns
S1S2S3S4S5
SNP S6loci S7S8S9S10S11S12

An unknown haplotype sample

P1 P2 P3 P4Suppose we wish to distinguish
an unknown haplotype sample.

: Major allele: Minor allele

10National Taiwan University
Department of Computer Scienceand Information Engineering

Examples of Tag SNPs
Haplotype pattern
S1S2
S3S4S5
SNP S6loci S7S8S9S10S11S12SNPs S1 and S12 can form aset of tag SNPs.
 This set of SNPs is theminimum solution in thisexample.

P1 P2 P3 P4

SNPs can work together
and help each otherP1 P2 P3 P4S1S12Our Approach

Our Approach
snp1 snp2 snp3
haplotype1

ACG

haplotype2

A

T

T

haplotype3

ACG

haplotype4

A

T

T

haplotype5

C

T

T

haplotype6

A

T

T

haplotype7

CTG

haplotype8

C

C

T

haplotype9

C

C

T

haplotype10

C

T

TC

GT

A

else

{ We introduce newallele AC and ¬ACTG: AC
0.7
0.1
0.8

AC00.2
0.2

0.7
0.3

{ Only one mistake11

Our Approach

Our Approachsnp1 snp2 snp3 snp4
haplotype1

ACGA

haplotype2

ATTC

haplotype3

ACGA

haplotype4

ATTC

haplotype5

CTTA

haplotype6

ATTC

haplotype7

CTGA

haplotype8

CCTC

haplotype9

CCTC

haplotype10

CT

T

A

{

(snp1, snp2) vs. snp3

AC , G: AC , T{(snp1, snp2) vs. snp4

(AC _ CT ) , A: (AC _ CT ) , C

Our Approach

In the Right OrderA group of individuals(all SNPs are known)
SelectA set of SNPs
(tag SNPs)

Relationships
between tag SNPs
and other SNPs

SecondFirst12Our Approach

Our Approach{ Generate relationships

If SNP 1, 4, 10 are tag SNPs
Predict SNP 17 with patterns …
Accuracy / LD: 0.97
If SNP 5, 8, 13 are tag SNPs
Predict SNP 11 with patterns …
Accuracy / LD: 0.62…………

Our Approach

How to Predict / Determine the Alleles?
{ LD: (tag) SNP 1, 2, 3 vs. SNP 4{ Allele A/a, B/b, C/c, D/dabc

PA B C D > PA B C d ) major
PA B cD < PA B cd ) minor¢¢¢SNP[123]becomesbi-allelicabCAbcaBc

AbCaBCABCABc

majorbucketminorbucket(AB C _ AbC _ Abc _ abC _ abc) = M ) D(AB c _ aB C _ aB c) = m ) d13

Our Approach

Similar Work
{ Ke Hao also did a similar workz The same LD modelz Different way to determine alleles forcomposite SNPs
{ Less flexibility{ A special case of our modelz

Related paper: “Genome-wide selection of tag SNPs using
multiple-marker correlation,” Bioinformatics, 2007

Our Approach

Sketch{ Get r2 value for all possiblecombinations{ Find a small subset of SNPs

according to LD14

Our Approach

Sketch{ Find a small subset of SNPs

according to LD

Tag SNPs
Tag SNPs arealso coveredby themselves

partialcoveredcovered

Our Approach

Sketch{ Simple greedy algorithm (Ke Hao)z Cover more SNPs in each iteration{ Modified greedy algorithm (my work)z A SNP that can’t be covered by others{ High priority

z A SNP that is not picked but covered{ OKz Break tie: partial cover15

Our Approach

SupersedeNo longer
contributesOur Approach

Supersede16

Our Approach

My Program: MMTagger
A lgor it hm 1 T wo-M ar k er M M Tagger
R equir e: set of t riplet s
1: w hi le t here are SNPs uncovered do
Pick a SNP
2:
if t here is a SNP s wit h no incoming edges t hen¤
3:s Ã s4:el se
5:s¤ Ã t he SNP t hat covers t he most uncovered SNPs
6:
for each t riplet s t of form (si ; sj B s¤ ) doremove t and it s corresponding edges
7:
8:
Put s¤ int o t ag SNP set/ * s¤ is \ picked"
9:for each t riplet s t of form (s¤ ; si B sj ) or (si ; s¤ B sj ) do
10:
i f si is picked t hen
11:
put sj int o covered SNP set
Data structure
12:
remove t and it s corresponding edges
13:
else
14:
remove all t riplet s of form (si ; s0 B sj ) or (s0; si B sj )*/Our Approach

Complexity{ Computing r2 valuez O(nk+1) for k-marker{ Picking tag SNPsz - (T ) where T is the number ofrelationshipsz O(T log T) time algorithm

17Result

Result{ Our program: MMTagger{ Vs. Single-marker approach (LRTag)z A state-of-the-art programz Single-marker{ Vs. Hao’s program (MultiTag)z Multi-marker

ResultVs. Single-Marker Approach18

Result

MMTagger Vs. MultiTagConclusion{ We provide a new multi-marker

modelz Size of tag SNP set{ 2- vs. 1-marker: apparently better{ 3- vs. 2-marker: slightly better{ 4-marker or more: slow, unacceptable{ Performancez Our program outperforms the only

other program with similar model19

Thank you!

ThankThank You
You

20