HTML

Az élet kódjai

Csináld maga. Senki nem csinálja meg helyetted.

Friss topikok

  • Kalle: @Travis.CG: Igazság szerint bioinformatikában nem is nagyon tudnék érvet mondani, hogy miért kéne ... (2019.06.28. 23:45) CentOS, nagyoknak
  • sdani: @Travis.CG: Nohát, nem is tudtam, hogy ilyen van... bár ahogy elnézem ezek a komponensek fizetősek... (2018.11.01. 10:14) Rossz beidegződések a bionformatikában
  • Csenge Tarnói: Ez érdekes. Most csinálok egy meta-analízist, életemben először, úgyhogy az én tudásom is felszíne... (2018.10.01. 21:39) Ez már nekem sok
  • robertherczeg: Nekem a kedvenc az volt, hogy: "Inkább eleve Mann-Whitney és/vagy Wilcoxon tesztet használjunk, m... (2018.09.04. 07:47) Ezért utálom a Wilcoxon-tesztet
  • Travis.CG: ÉÉÉÉÉs megjelent! (2018.08.24. 23:31) Nehéz szülés 2

Markov láncok

2019.06.30. 13:08 Travis.CG

Szerepjátékos koromban a legnagyobb kihívást a jó karakter nevek kitalálása okozta. Rendszeresen valami nyögve nyelős, erőltetett nevet találtam ki, ami általános derültséget váltott ki a csapatban. Ha akkor ismertem volna a Markov láncokat, mindez nem jelentett volna problémát.

A Markov láncok nagyon egyszerűek: Semmi más, mint egymást követő elemek. Azt, hogy miként követik egymást az elemek, valószínűségekkel adjuk meg, amit átmeneteknek nevezünk. Vegyünk például egy tornasort. A magasabbak elől állnak, az alacsonyabbak hátul. Annak a valószínűsége, hogy a legmagasabb valaki után következzen, nulla. Tegyük fel, több, azonos magasságú ikerpár is van ezen a tornaórán. Az ő átmenetét 0.5-el jellemezhetjük, mert hol az egyik van előrébb, hol a másik.

A Markov láncok általában csak az egymást közvetlenül követő elemekre adják meg az átmeneteket, vagyis a korábbi elemek nem számítanak. Ez akkor érdekes, ha nem egy tornasorra gondolunk, hanem más hosszú láncokra, amelyek viszonylag kevés elemből állnak. Mint amilyen a DNS is.

A Markov láncok segítségével bármilyen hosszú DNS-t jellemezhetek, hiszen csak azt kell megadnom, hogy egyik nukleotid milyen valószínűséggel követi a másikat. Ha a nukleotidok teljesen random követnék egymást, akkor ez nem lenne túl érdekes, mert az átmenetek csak 0.25-t tartalmaznának. De tudjuk, hogy a kódoló és nem kódoló szakaszoknál ez más, sőt fajokban is eltérhet!

Tehát ha az átmeneteket egy mátrixba gyűjtöm, akkor bármilyen hosszú DNS szekvenciát jellemezni tudok. A mátrix mérete nem változik.

Sőt, a szabály ismeretében bármilyen hosszú DNS szekvenciát is tudok generálni. Ennek persze nem sok értelme van, és nem is segíti a megértést, ha szekvenciákkal szemetelem tele a képernyőt, ezért inkább Gyűrük Ura neveket fogok generálni demonstrálásként, amiket fantasy játékokban lehet használni.

Először is szükségünk van az átmenetekre. Ezeket már létező nevekből kapjuk meg. A Wikipédiaból kimásoljuk az összes nevet. Én eltávolítottam az összes ékezetet, kötőjelet és angol kötőszót, majd a szöveget kisbetűssé változtattam. Minden név egy sorban van.

import sys
import random

transition = dict()
letters = set()

for i in open(sys.argv[1]):
   name = i.rstrip()
   for j in range(1,len(name)):
      pch = name[j-1]
      ch = name[j]
      if pch not in transition:
         transition[pch] = dict()
      if ch not in transition[pch]:
         transition[pch][ch] = 0
      transition[pch][ch] += 1
      letters.add(pch)

A transition nevű változó fogja tárolni az átmeneteinket. Most még csak az átmenetek számát tartalmazza. Ebből nekünk valószínűségeket kell kapnunk.

for ch1 in transition:
    s = 0
    for ch2 in transition[ch1]:
       s += transition[ch1][ch2]
    for ch2 in transition[ch1]:
       transition[ch1][ch2] = float(transition[ch1][ch2]) / s

Gyakorlatilag ez egy normalizálás, hogy 0 és 1 közötti értékeket kapjunk. Már csak a generálás van hátra. Ebben a programban csak 5 betűs neveket készítünk, de lehet kísérletezni más hosszúsággal is.

letters = list(letters)
ch1 = letters[random.randint(0, len(letters)-1)]
name = ch1
for i in range(5): # Length of the name
   r = random.random()
   s = 0.0
   if ch1 not in transition:
      break
   for ch2 in transition[ch1]:
      s += transition[ch1][ch2]
      if r < s:
         ch1 = ch2
         name = name + ch2
         break
print(name)

Néhány példa, hogy mi jött ki: Marwor, Frindo, Halanb, Brisen. Persze vannak teljesen használhatatlan nevek is: Hbelfr, Rgoron, Wirorf, Ndunha.

A bemeneti adatok most az összes karakter nevét tartalmazzák. Biztos érdekes lehet csak tünde, vagy csak hobbit neveken lefuttatni. Esetleg ha elég nagy listánk lenne, akkor nemek szerint is bonthatnánk. A következő posztban kicsit fejlesztjük a koncepciót és bemutatom a rejtett Markov láncokat.

Szólj hozzá!

Címkék: statisztika

A bejegyzés trackback címe:

https://cybernetic.blog.hu/api/trackback/id/tr3514916352

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.