Két betűsort egymás alá írva könnyű megszámolni, hány pozíción áll eltérő jel. Ha azonban az egyik sorba közben bekerült egy új karakter, a későbbi jelek eltolódnak. Egyetlen beszúrás így több pozíciónkénti eltérésnek látszhat.
A következő nagyon rövid sorozatok mesterséges, oktatási karakterláncok: ACGTAC és ACGTTAC. Nem származnak valódi mintából vagy élőlényből. A cél az összehasonlítási módszer megértése; a példából sem eredetet, sem működést, sem biológiai változás tényleges történetét nem állapítjuk meg.
Az eltérő hossz már az elején fontos adat
Az első sor hat, a második hét karakteres. A szokásos Hamming-távolság azonos hosszúságú sorok pozíciónkénti eltéréseit számolja, ezért erre a különböző hosszúságú párra közvetlenül nem alkalmazható.
Ha mégis csak az első hat pozíciót vetnénk össze, az ötödik és a hatodik helyen eltérést látnánk. Ehhez még hozzászámolhatnánk a megmaradó hetedik jelet, és három különbséget mondhatnánk. Ez azonban egy önkényes összehasonlítási szabály volna, nem a standard Hamming-távolság.
A hossz megtartása az adatok között ezért alapvető. A sorok hosszának automatikus kiegyenlítése, például a hosszabb sor végének eldobása az eltérés okát is elfedheti.
Egy beszúrással pontosan megkapható a második sor
Az ACGTAC negyedik karaktere után egy további T beszúrásával ACGTTAC keletkezik. Egyetlen szerkesztési művelet elegendő, ezért az egységnyi beszúrási, törlési és helyettesítési költséggel számolt Levenshtein-távolság 1.
Az érték nem lehet nulla, mert a két karakterlánc eltér. Egy művelettel létrehoztunk pontos egyezést, ezért az egyes távolság minimális. Ez rövid, teljesen ellenőrizhető bizonyítás a két saját karakterláncra.
A megismételt T miatt a rés elhelyezése nem feltétlenül egyedi: a szomszédos azonos jelek között több azonos költségű igazítás is adódhat. A minimális műveletszám ettől változatlan marad. Az igazítás helyét ezért sem szabad automatikusan egy tényleges biológiai esemény bizonyítékának tekinteni.
A helyettesítés másfajta eltérést ad
Hasonlítsuk össze az ACGTAC és ACCTAC sorokat. Mindkettő hat karakter hosszú, és csak a harmadik pozíció különbözik: G helyett C szerepel. A Hamming-távolság 1, az egységköltséges Levenshtein-távolság szintén 1.
A két távolság egyezése ebben a példában nem jelenti, hogy minden feladatra felcserélhetők. A megengedett műveleteket és azok költségét előre kell meghatározni. Biológiai igazítóeljárások más helyettesítési és résbüntetési szabályokat is használhatnak.
Az NLM szekvenciaigazítási útmutatója külön jelöli az eltéréseket és réseket. A BLAST pontozását itt nem azonosítjuk az egyszerű Levenshtein-távolsággal; a jelen példában minden szerkesztés választott költsége egy.
A GC-arány nem távolságmérték
Az első ACGTAC sorban három G vagy C karakter van a hatból, ezért a GC-arány 50%. Az új T beszúrása után továbbra is három G vagy C szerepel, de a nevező hétre nő: 3/7 × 100 ≈ 42,86%.
A DNS-szekvencia-elemző a hossz és az összetétel ellenőrzéséhez használható. Ebből nem következik, hogy teljes szekvenciaigazítást vagy Levenshtein-távolságot is számol. A szöveg-összehasonlító megjelenített különbségeit pedig a saját összehasonlítási szabálya szerint kell értelmezni.
A különböző GC-arány önmagában nem mondja meg, hol történt eltérés. Ugyanígy két azonos összetételű karakterlánc sorrendje is különbözhet. A hossz, az összetétel és az igazítás három külön ellenőrzési szempont.
Azonos hossz és GC-arány mellett is lehet nagy a pozíciónkénti eltérés
Hasonlítsd most össze az ACGTAC és CACGTA karakterláncokat. Mindkettő hatkarakteres, és mindkettőben két A, két C, egy G és egy T szerepel. A GC-arány mindkét esetben 3/6 = 50%. A betűk sorrendje azonban eltér.
| Pozíció | ACGTAC | CACGTA |
|---|---|---|
| 1. | A | C |
| 2. | C | A |
| 3. | G | C |
| 4. | T | G |
| 5. | A | T |
| 6. | C | A |
Mind a hat helyen más karakter áll, így a Hamming-távolság 6. A Levenshtein-távolsághoz viszont megengedjük az egységköltséges beszúrást és törlést is. Két művelet elegendő:
| Állapot | Karakterlánc | Az előző sorból végzett művelet |
|---|---|---|
| Kiindulás | ACGTAC | Nincs |
| Köztes sor | CACGTAC | Egy C beszúrása az elejére |
| Cél | CACGTA | Az utolsó C törlése |
A Levenshtein-távolság tehát legfeljebb 2. Nulla nem lehet, mert a sorok különböznek. Egyetlen beszúrás vagy törlés megváltoztatná a hosszt, miközben a két végső sor hossza azonos. Egyetlen helyettesítés csak egy pozíciót javítana, itt pedig hat különbözik. Egy művelet ezért nem elegendő, a minimális távolság pontosan 2.
A NIST Hamming-definíciója a megfelelő pozíciók eltéréseit, a NIST Levenshtein-definíciója a szükséges beszúrások, törlések és helyettesítések minimális számát rögzíti. A kétféle eredményt ezekkel a szabályokkal kaptuk ugyanarra a saját karakterláncpárra.
Ha egy összesítő mindkét sorra csak 6 karaktert és 50% GC-arányt közöl, az adatok még nem igazolják a sorozatok azonosságát. Pozíciónkénti hibákhoz a Hamming-érték, megengedett beszúrásokkal és törlésekkel végzett összevetéshez a választott szerkesztési távolság válaszol a kérdésre. A kétműveletes előállítás ebben a példában is matematikai összehasonlítás; a tényleges keletkezési történetre nem ad bizonyítékot.
Gyakori kérdések
Miért nincs itt közvetlen Hamming-távolság az első párra?
A két sor hossza eltér. A standard pozíciónkénti Hamming-összehasonlítás azonos hosszúságú sorokat igényel.
A minimális egy beszúrás megadja a valódi változás történetét?
Nem. Ez a két megadott karakterlánc között, a választott költségmodellben elégséges minimális szerkesztés. Történeti következtetéshez más adatok is kellenek.
A GC-arány változásából megmondható a beszúrt jel helye?
Nem. Az összetételi arány nem tartalmaz helyinformációt. A karakterek sorrendjét és az igazítást külön kell megvizsgálni.
Záró tudáspróba
Válassz kérdésenként egy választ. A megoldások ellenőrzése után minden helyes válaszért 1 pontot adj magadnak; a hibás, kihagyott vagy több válasszal megjelölt kérdés 0 pont. Összesen 0–3 pont szerezhető.
1. Miért nem adunk standard Hamming-távolságot az ACGTAC és ACGTTAC párra?
- A) Mert a sorokban T karakter szerepel.
- B) Mert a GC-arányuk eltér.
- C) Mert hat-, illetve hétkarakteresek, a standard Hamming-távolsághoz pedig azonos hossz kell.
2. Mennyi az ACGTAC és CACGTA pár Hamming-, illetve egységköltséges Levenshtein-távolsága, ebben a sorrendben?
- A) 6 és 2.
- B) 2 és 6.
- C) 0 és 0.
3. Mit igazol a két hatkarakteres sor azonos, 50%-os GC-aránya?
- A) A karakterek minden pozícióban megegyeznek.
- B) Mindkét sorban három G vagy C van; a karakterek sorrendjét ez önmagában nem határozza meg.
- C) A két sor Levenshtein-távolsága biztosan nulla.
Megoldások és pontszám
1. C. A Hamming-távolság a megfelelő pozíciók eltéréseit azonos hosszúságú sorok között számolja. A hosszabb sor levágása más feladatot hozna létre; az eredeti pár egységköltséges Levenshtein-távolsága ugyanakkor 1.
2. A. Mind a hat megfelelő pozíció eltér, ezért a Hamming-távolság 6. Egy kezdő C beszúrása és a végső C törlése két szerkesztés; egyetlen művelet a cikkben levezetett hossz- és pozíciófeltételek miatt nem elég. A Levenshtein-távolság így 2.
3. B. Hat karakter 50%-a három G vagy C. Az arány a mennyiséget összesíti, helyinformációt nem őriz meg. Az ACGTAC és CACGTA éppen olyan ellenpélda, amelynek összetétele azonos, sorrendje eltér.
3 pont: A hosszfeltételt, a szerkesztési műveleteket és az összetételi mutató korlátját is felismered. Próbaként írd le önállóan a CACGTAC köztes sort, és ellenőrizd, melyik két egykarakteres művelet kapcsolja a két végső sorhoz.
2 pont: Két összehasonlítási szempont helyes. Az 1. kérdéshez az eltérő hossz feltételét, a 2.-hoz a hatpozíciós és a háromállapotos táblázatot, a 3.-hoz a GC-arány értelmezését olvasd újra. A javított válaszban nevezd meg a használt összehasonlítási szabályt.
0–1 pont: Először számold meg minden sor hosszát. Az ACGTAC és CACGTA párnál külön sorban jelöld a hat pozíciónkénti eltérést, majd külön vezesd le a két szerkesztést. Végül mindkét sorban számold össze a G és C karaktereket; így a három vizsgálat eredménye elkülönül.