名古屋大集中講義 iwatawiki lec03 s





• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 



2016/11/29 13:00-14:30














vs.
• 


–  DNA





• 
– 
• 
• 








• 
QTL
7


8





2

• 
– 




DNA

12

8



24

Kurata and Omura (1982) Jpn J Breed 32:253

46

DNA

h8p://wkp.fresheye.com/wikipedia/

1







1

3

7



8
4
" 8%
P(X = 4) = $ ' × 0.34 × 0.7 4
# 4&
1-p

p




B C

" n%
n!
$ '=
# k & k!(n − k)!

0.30
0.20
0.15

P(X=k)





0.10

C

0.05

B

p=0.3, n=8

0.25

" n%
P(X = k) = $ ' p k (1 − p) n −k
# k&
A

0







k

0.00

n

2

4
k

6

8

p
8
4

1

1 1

2

2

2

2

2

3

3

" 8%
P(X = 4 | p) = $ ' p 4 (1 − p) 4
# 4&

3

i
n


# 8&
L( p | X = 4) ∝ P(X = 4 | p) = % ( p 4 (1 − p) 4
$ 4'



3

P(X1 = 3, X 2 = 3, X 3 = 3) =


p

2

9



p

5

9!
× 0.33 × 0.5 3 × 0.2 3
3!3!3!

i=1,2,…,k
i



xi

pi

k
n!
n!
x1
xk
P(X1 = x1,..., X k = x k ) =
p1  pk =
pix i

x1! x 2!
x1! x 2! i

-2
-3
-4

log(p)

-1

0



0.0

0.2

0.4

0.6

0.8

1.0

9

p

3

ln L(p)

L(p)

• 

p1,p2,p3
p1,p2,p3

ln L(p)

ln L( p) = 4 ln p + 4 ln(1 − p) + const
ln L( p1, p2 ) = 3ln p1 + 3ln p2 + 3ln(1 − p1 − p2 ) + const
-10
-14

p=0.5

-18

4 ln(p) + 4 ln(1-p)

-6

d ln L( p)
(1− 2 p)
=4
=0
dp
p(1− p)

0.0

0.2

0.4

0.6
p

0.8

1.0

$1
' (1 − 2 p1 − p2 )
∂ ln L( p1, p2 )
1
= 3& −
=0
)=
∂p1
% p1 1 − p1 − p2 ( p1 (1 − p1 − p2 )
$1
' (1 − p1 − 2 p2 )
∂ ln L( p1, p2 )
1
= 3& −
=0
)=
∂ p2
% p2 1 − p1 − p2 ( p2 (1 − p1 − p2 )

p1=1/3, p2=1/3, p3=1/3





F2
AB
0.5(1-r)

Ab
0.5r

aB
0.5r

ab
0.5(1-r)

AB
0.5(1-r)

AABB
(1-r)2

AABb
r(1-r)

AaBB
r(1-r)

AaBb
(1-r)2

Ab
0.5r

AABb
r(1-r)

AAbb
r2

AaBb
r2

Aabb
r(1-r)

aB
0.5r

AaBB
r(1-r)

AaBb
r2

aaBB
r2

aaBb
r(1-r)

ab
0.5(1-r)

AaBb
(1-r)2

Aabb
r(1-r)

aaBb
r(1-r)

aabb
(1-r)2

1/4

F2
A

A
1 P1
B

×

B

a

a

b

b

A

a

B

b

2 P2

1

AA


Aa

aa

BB

(1-r)
2
30

2r(1-r)

7

r 2
2

Bb

2r(1-r)

5

2{r
2+(1-r)2}
57

2r(1-r)

6

bb

r 2
1

2r(1-r)

8

(1-r)
2
29

F1


A

A

1



B

b

0.5(1-r)

0.5r

a

1/4

a





2

B

b

0.5r

0.5(1-r)


F2






r:



9

145



ln L(r) = 30ln(1− r) 2 + 7ln2r(1− r) +  + 29ln(1− r) 2 + const
= 144 ln(1− r) + 32ln r + 57ln(1− 2r + 2r 2 ) + const



ln L(r) = 144 ln(1− r) + 32ln r + 57ln(1− 2r + 2r 2 ) + const

-130

LOD

–  AC

rˆ = 0.117

600

-150

0.2

0.3

0.4

0.5

2

– 
0.0

0.1

0.2

0.3

0.4

M
(cM)
Kosambi

0.5

r

odds
L(0.5)

L( rˆ ) /L(0.5)

2

x
x

r

LOD


BC
)

(



-200 0

0.1

AB

• 

200

-170

0.0



• 

1000

ln L(r) - const

-110

d ln L(r)
144 32 57(4r − 2)
=−
+ +
dr
1− r r 1− 2r + 2r 2

–  Haldane






" L( rˆ ) %
LOD = log10 $
' = log10 L( rˆ ) − log10 L(0.5) = 26.8
# L(0.5) &

Haldane



Kosambi



1
x = − ln(1− 2r)
2
1 #1+ 2r &
x = ln%
(
4 $ 1− 2r '






0.1

0.2

0.3

0.4

0.5

r

1
2




3



4



m

a
m

a
a m

b

0.4

r = x


a m
b m

b

0.0

0.2

0.4

0.6

0.8

1.0

x (M)

r



m f(x)=0


b

a b

Haldane

0.3

a



0.2

1000
600
-200 0 200
0.0

Kosambi

0.1



r



0.0

0

f(x)=0
x

1.  f(a) f(b)
b

2.  a b
m
3.  f(m)
f(a)
f(b)

4.  2-3

r

∂ ln L(r)
144 32 57(4r − 2)
=−
+
+
∂r
1− r r 1− 2r + 2r 2

0.5

(bisec]on method)

Newton-Raphson



.
%

05
2

1.2


1. 



L1

0.0

• 


2. 
3.  LOD
4.  LOD
(linkage groups)




L2

5.2

L3

8.3








L1-L2-L3-L4-L5-L6


1

• 


5. 
6. 
7. 
8. 

• 



L4

14.5

L5

17.1

L6

20.3




• 







• 



• 

1. 

– 

LOD

l −1



L( R)=∑ ni ,i +1[θ i ,i +1 log θ i ,i +1 + (1 − θ i ,i +1 ) log(1 − θ i ,i +1 )]

2. 

i =1

LOD

– 


3.  1 2

Maximum Likelihood

frac]on SARF

Minimum sum of adjacent recombina]on
l −1



SARF = ∑ θ i ,i +1
i =1

θi,i+1


ni,i+1


.


(global op]mal solu]on, local op]mal solu]on)






L1

L1

L1






L2

L3

L3






L2

L3




L2



L4

L4



L1-L3-L2-L4


L4





Traveling salesman problem (TSP)




¡ 
l 
l 
l 

10
… 1,804,400
100 … 4.7 x 10158
1000 … 2.0 x 102567
MAPMAKER

• 





combinatorial op]miza]on problem









c

c

a
t
k
q
p



k


5
5!/2
= 60



t

5



q
p

1



v
r







13,509

500



h8p://www.crpc.rice.edu/newsArchive/tsp.html


(ant colony op]miza]on: ACO)

t

• 

k
ij

k

p (t ) =

• 

i

j

[τ ij (t )]α [dij ]− β

∑l∈N k [τ il (t )]α [dil ]− β

∀j ∈ Nik .

i

• 

d ij

τ ij (t )

• 







ACO
1. 
2. 

3. 

2

4. 




5. 

1 4
m



τ ij (t + 1) = ρτ ij (t ) + ∑k =1 Δτ ijk (t )

F

B

ρ 1







A

C

E



k

⎧Q Lk (t ) if (i, j ) ∈ T k (t )
Δτ (t ) = ⎨
if (i, j ) ∉ T k (t )
⎩0
k
ij











bootstrap




AntMap



•  AntMap

•  RGP Web

• 

h8p://rgp.dna.affrc.go.jp/
AntMap





•  AntMap

/

DHLs 169






/Kasalath//

BILs 245




OS Windows, Mac, Linux,

• 
Solaris

Java
h8p://lbm.ab.a.u-tokyo.ac.jp/~iwata/antmap/



/IR24 RILs 375




(Swarm intelligence)


• 

① 2.5
② 3
③ 7

– 
– 
– 



• 



CPU Intel Mobile Pen]um 1.6GH

•  100
– 







• 


③ 38

• 

① ②
5, 2, 5







(par]cle swarm op]mizer: PSO)


•  1,200
•  10
2.5




• 



• 



• 

• 


PSO



wv t−1

R code
B

c 2 r2 (x g − x)

A x

vt
c1r1 (x p − x)

xg

C

f (x)
A
x p




$
x t ← x t−1 + v t
%
& v t ← wv t−1 + c1r1 (x p − x) + c 2 r2 (x g − x)

w, c1, c2
r1, r2

1
[0, 1]

(w < 1)




# load required packages
require(rgl)
require(pso)
# set x and y arrays
x
Show more