Multi point calculation using F ourier T ransforms

between marker 1 and 2. In the gure

v 2 = w ₃

^{is updated according to all}

statesof

v ₁

^.

The idea behind multi point analysis is that we exploit thefact that few

crossoversaremost likelyto occurbetween two markers, sincethe

recombina-tionfractionbetweentwoadjacentmarkersisalwayslessthan

1 2

^{. Forinstance,}

if we have observed the exact state of

v ₁

^as

v ₃

^{, that is}

P ( v ₁ = v ₃ |G ₁ ) = 1

^,

thentheprobabilityofall inheritancevectorsat

v 2

^close24to

v ₃

^getincreased

probability,whereasinheritancevectorsfar 25

from

v ₃

^getdecreasedprobability. More precisely, the contribution from any state

v _i

^of

v ₁

^{is given by the}

probability oftheinheritance vector at marker1conditioned on thegenotype

informationat thatlocus,

P (v _i |G ₁ )

^{,timesthetransition}probability

P (w ₃ | v _i )

^.

The transition probability is given by the Hamming distance between the

two inheritance vectors which indicates the number of odd crossovers that

have occurred between two markers on a chromosome. The probability of

d

crossoversoccurringbetweentwo markerswithaninheritance vectoroflength

n

^is

θ ^d ₁ · (1 − θ ₁ ) ^{n − d}

^.

We thensum over thecontribution to

w ₃

^{of every vector}

v _i

^{, which}

corre-spondsto marginalizing out

v ₁

^{. The sum inthen multiplied with the}

condi-tionalprobabilityof

w ₃

^given

G 2

^{. Thisproductis}proportionalto

P (w ₃ |G 1 , G 2 )

^.

We compute this product for every inheritance vector at marker

M ₂

^to

getthe full probability distribution,

P ( v ₂ |G ₁ , G ₂ )

^{26. Theupdated} probability distribution at marker 2 can then be used to calculate the left-conditioned

probability at marker 3 and so forth. The right-conditioned probability is

calculatedinat similar fashion.

Using this procedure we can compute

P( v i |G all )

^{for any}

v i

^{. Thesevalues}

canthenbeusedinthescoringfunctions,i.e. LODscore,todeterminelinkage

between markers and traits.

where

|v|

^{isthe numberof} inheritance vectors. A convolution hasto be done twice for each marker: Once for calculating the left conditioned probability

andoncefor the right conditioned probability.

In[Gud00 ]Gudbjartssonshowshowthe algorithmsforFastFourier

Trans-forms can berewritten for better utilisation of CPU cache and registers with

speeds-upranging fromafactor of1.9 to5.3dependingon thedataanalysed,

[Gud00 ,page 32-34]. The speed-ups areobtained througha reordering of the

computationssothat they take advantage ofthe cache memory,and through

unrollingloopswhich reduces the amount of book-keeping.

For more on Fourier Transforms within the eld of linkage analysis, see

[KL98 ]and [Gud00 ].

3.4.4 Founder Reduction

One way of reducing the number of computations for the set of inheritance

vectorsfor a pedigree isbyapplying thesocalled founderreduction, [Gud00,

page34]. Theintuitiveideaisthatconsistentlychangingtheallelepointingto

afounder, frompaternal to maternaland viceversa for all children, yields an

newinheritance vector withthesame probability astheoriginal vector. This

isbecause we cannotdistinguish between maternaland thepaternal alleles of

founderssince the phaseis unknown.

Noticethatitisnotareductioninthenumberofinheritancevectors,rather

anexploitation of symmetriesinthe probabilitydistribution.

For the

{ p, m }

^{describing paternal and maternal} inheritance we dene in-versionsuchthat:

p = m

^and

m = p.

Thefounderreductionappliesfor anyfounder,butfor convenience we just

state the reduction for one male founder. The reduction for all founders is

equivalent. Stated formally:

Theorem 6 (Founder Reduction) Let

h ∈ F

^{be a male founder in some}

pedigree

P = h F, N, f ather, mother i

^{. Let}

C

^{denote the set of children of}

h

^,

thatis

C = { n ∈ N | f ather(n) = h }

^{. Let}

v

^and

w

^{be two} inheritance vectors, suchthat for any

n ∈ N

^:

w(n, p) =

( v(n, p) : n ∈ C v(n, p) :

^otherwise;

w(n, m) = v(n, m).

Givensomegenotypeinformation

G = hL, astatesi

^{onthepedigreethefollowing}

alwaysholds:

P(v |G ) = P(w |G ).

^(3-21)

Intuitively,thedenitionof

v

^and

w

^{statesthatifachildof}

h

^hasinherited

h

^{'s paternal allele according to}

v

^{, then that child has inherited}

h

^{'s maternal}

allelein

w

^{,and viceversa.}

Proof: Prior to proving for multi point linkage analysiswe prove thatit

holds for single point linkage analysis. The denition of

v

^and

w

^{implies the}

following relationship between

F ^v

^and

F ^w

^:

F ^w (n, $) =

 



 

(h, m) : F ^v (n, $) = (h, p) (h, p) : F ^v (n, $) = (h, m) F ^v (n, $) :

^otherwise

,

where

$ ∈ { p, m }

^{. Theorem1 statesthat:}

ϕ ^v _G ^def = ^

n ∈L

(f _F v ( n,p ) = a ₁ ∧ f _F v ( n,m ) = a ₂ ) ∨ (f _F v ( n,p ) = a ₂ ∧ f _F v ( n,m ) = a ₁ ) ,

where

a ₁ , a ₂ ∈ astates(n)

^{. By denition}

ϕ ^w _G

^{is equal to}

ϕ ^v _G

^{with regard to all}

sub-expressions,exceptthatanysub-expression:

(f _h,$ = a ₁ ∧ f _n,$ 0 = a ₂ ) ∨ (f _h,$ = a ₂ ∧ f _n,$ 0 = a ₁ ),

in

ϕ ^v _G

^lookslike:

(f _h,$ = a ₁ ∧ f n,$ ⁰ = a ₂ ) ∨ (f _h,$ = a ₂ ∧ f n,$ ⁰ = a ₁ ),

in

ϕ ^w _G

^{. Thismeans that any} constraints on founder allele

(h, $)

ⁱⁿ

ϕ ^v _G

^{is also}

aconstraint on

(h, $)

ⁱⁿ

ϕ ^w _G

^.

Thisimpliesthatforanyfounderalleleassignment,

Z M

^{,whichsatises}

ϕ ^v _G

that assigns the allelic state

a

^to

(h, $)

^{, there exists a similar founder allele}

assignment with equal probability,

Z _M ⁰

^{, which satises}

ϕ ^w _G

^{that assigns the}

allelicstate

a

^to

(h, $)

^{. Inother words:}

∀ Z _M ∈ [[ϕ ^v _G ]] ∃ Z _M ⁰ ∈ [[ϕ ^w _G ]] ∀ n ∈ F. Z _M ⁰ (n, $) = (

Z M (n, $) : n = h Z _M (n, $) :

^otherwise,

fora xed

h

^{. Theoppositeisalso truesincewecan applythesame argument}

using

v

^as

w

^and

w

^as

v

^{. F}urthermore,

P (Z _M ) = P (Z _M ⁰ )

^{since they assign}

exactlythe same set of allelic states to founder alleles, which in turnimplies

that:

X

Z _M ∈[[ ϕ ^v _G ]]

P(Z _M ) = X

Z _M ⁰ ∈[[ ϕ ^w _G ]]

P (Z _M ⁰ )

andfrom (3-5)we deduce:

P(v |G ) = P(w |G ).

case. To do this we use the fact that founder reduction holds in the single

point case, thatis weusethat(3-22)holds. We considertwo markers

M ₁

^and

M ₂

^{withcomputed single point} probabilities. We prove that transferring the probabilities from

M ₁

^to

M ₂

^{preserves the equalitybetween the} probabilities of the two inheritance vectors

v ₂

^and

w ₂

^{, where}

v ₂

^and

w ₂

^are inheritance vectors for marker

M ₂

^{, and}

v ₂

^and

w ₂

^{are dened at}

v

^and

w

^, respectively, in Theorem 6. Hence, we want to show that two inheritance vectors in the

sameequivalence class,due tothefounderreductionat marker

M ₂

^,remainin

the same equivalence class after we have propagated the evidence (genotype

information)observed at marker

M ₁

^.

Assumethatavector,

v ₁

^,issomeinheritancevectorformarker

M ₁

^,and

w ₁

isdened intermsof

v ₁

^{asdescribedin Theorem6. Observe that}

P (v ₁ |G ₁ ) = P(w ₁ |G ₁ )

^{, and}

P (v ₂ |G ₂ ) = P (w ₂ |G ₂ )

^{due to (3-22), where}

G ₁

^and

G ₂

^{are the}

genotype information for marker

M ₁

^and

M ₂

^,respectively. We want to show that:

P (v ₂ |G ₁ , G ₂ ) = P (w ₂ |G ₁ , G ₂ )

^(3-23)

Lettherecombinationfractionbetween

M ₁

^and

M ₂

^be

θ ₁

^{. Then}

contribu-tion in terms of probability from

v ₁

^to

v ₂

^{is given by}

θ ₁ ^{d v} (1 − θ ₁ ) ^{n − d v}

^{, where}

d _v = Ham(v ₁ , v ₂ )

^{is the Hamming distance between thevectors and}

n

^{is the}

lengthofaninheritance vector forthe pedigree. To showthat(3-23) holdswe

needtoshowthatthecontributionof

v ₁

^and

w ₁

^totheprobabilityof

v ₂

^,is

ex-actlythesameasthecontributionof

v ₁

^and

w ₁

^to

w ₂

^{. Todothisweprovethat}

Ham(v ₁ , v ₂ ) = Ham(w ₁ , w ₂ )

^{and that}

Ham(v ₁ , w ₂ ) = Ham(w ₁ , v ₂ )

^,because

this implies that

v ₂

^and

w ₂

^{are updated with exactly the same} probabilities given the observed genotype for

M ₁

^{. We only prove this for}

Ham(v ₁ , v ₂ ) = Ham(w ₁ , w ₂ )

^{sincethe oppositeis similar.}

The value

w ₁

^and

v ₁

^{are identical for all}

(n, $)

^{, except inthe case where}

$ = p

^and

f ather(n) = h

^{, in which case the value diers. Since the same}

appliesfor

v ₂

^and

w ₂

^weneedonlyconcentrateonHammingdistancesbetween theinheritance vectorsforchildrenof

h

^{. Forany}

(n, $)

^if

v ₂ (n, $) 6 = v ₁ (n, $)

then,bythe denitionof

w ₂

^and

w ₁

^{itfollowsthat}

w ₂ (n, $) 6 = w ₁ (n, $)

^{. The}

same argument applies for parts of the inheritance vectors where

v ₂ (n, $) = v ₁ (n, $)

^{. Inthiscase, bydenition}

w ₂ (n, $) = w ₁ (n, $)

^{,hencetheHamming}

distancebetween

v ₁

^and

v ₂

^{isequalto theHammingdistancebetween}

w ₁

^and

w ₂

^.

The same can be shown for

Ham(v ₁ , w ₂ ) = Ham(w ₁ , v ₂ )

^{with the same}

arguments. For this reason, in the multi point step the founder reduction

holds.

♦

In[Gud00 ]Gudbjartssondenesfoundercouplereduction asanadditionalway

of reducing the number of computations performed during single and multi

point linkage analysis. Intuitively, founder reduction states that we cannot

distinguish between the maternal and paternal alleles of founders, that is,

we can switch between their two alleles. Founder couple reduction states,

intuitively,thatwecannotdistinguishthemaleandfemalefounderofafounder

couple. Afounder couple istwo founderswho share ospringinthepedigree.

Westate this formallyinthefollowing theorem:

Theorem 7 (Founder Couple Reduction) Let

h, h ⁰ ∈ F

^{be the male and}

femalefounder,respectively, of a founder couple insome pedigree

P = hF, N, f ather, motheri

^{. Let}

C

^{denote theset of childrenof}

h

^and

h ⁰

^{, that}

is

C = { n ∈ N | f ather(n) = h

^and

mother(n) = h ⁰ }

^{. Let}

v

^and

w

^{be two}

inheritance vectors, suchthat for any

n ∈ N

^:

w(n, $) =

 



 

v(n, $) : n ∈ C

v(n, $) : f ather(n) ∈ C

^or

mother(n) ∈ C v(n, $) :

^otherwise

.

Given some genotype information

G = hL, astatesi

^{on the pedigree where}

h, h ⁰ ∈ L /

^{and that neither}

h

^nor

h ⁰

^{has any children in}

V

^{not in}

C

^{, the}

followingalways holds:

P(v|G ) = P(w|G ).

^(3-24)

We do not prove this, but refer the keen reader to [Gud00 , page 35] for

moreinformation on foundercouple reduction.

In document BRICS Basic Research in Computer Science (Sider 69-73)