PORAVNAVA NIZOV IN DELANNOYJEVA ŠTEVILA
MARKO RAZPET
Pedagoška fakulteta v Ljubljani
Math. Subj. Class. (2010): 05A15, 40B05, 68R15, 92D20
Pokazali bomo, kako je poravnava nizov povezana z Delannoyjevimi števili D(m,n), s
katerimi zapǐsemo število mrežnih poti v množici N×N od točke (0, 0) do dane točke (m,n),
pri čemer so dovoljeni koraki v smereh (1, 0), (0, 1) in (1, 1). Vpeljali bomo Levenštejnovo
razdaljo med nizoma in na kratko predstavili njeno uporabo v genetiki.
SEQUENCE ALIGNMENT AND DELANNOY NUMBERS
We will show how the sequence alignment is connected with the Delannoy numbers
D(m,n) which express the number of lattice paths in the set N × N with allowed steps
(1, 0), (0, 1) and (1, 1). The Levenshtein distance between two sequences is introduced
and its application in genetics is briefly presented.
Uvod
Kdor pǐse z računalnǐskim urejevalnikom besedil, zagotovo pozna poravnavo
vrstic: levo, desno, sredinsko in obojestransko. Po navadi imamo najraje
obojestransko poravnano besedilo, pri čemer sta vnaprej določena levi in
desni rob, ki nam kot vidna ali nevidna ravna črta ne dovoljujeta, da bi
kakšna črka, številka, ločilo ali kakšen drug znak padel bolj v levo od levega
roba oziroma bolj v desno od desnega roba. Pomembno vlogo pri tem igra
tudi znak za presledek, kateremu je namenjena posebna tipka. S presledki
na primer ločujemo besede in nakažemo nov odstavek, lahko pa si mislimo,
da z njimi na desno poravnamo prekratko vrstico. Ker običajno prostori za
grafične znake niso enake širine, del težav s poravnavo odpade, ker urejeval-
niki po potrebi sami rahlo zgoščajo in redčijo razmike med znaki.
Če pa izberemo znake, ki zahtevajo enake širine, potem imamo z obo-
jestransko poravnavo take težave kot nekoč na klasičnih pisalnih strojih.
In ravno taka poravnava nas bo v nadaljevanju najbolj zanimala. Spoznali
bomo, da je poravnava besed oziroma nizov kar uporabna. Vpeljemo namreč
lahko mero, koliko sta si niza blizu. Ker pa so znaki ali elementi niza lahko
marsikaj, lahko preverjamo ne le podobnost besedil in s tem odkrivamo na
primer plagiatorstvo, ampak tudi podobnost tonskih zapisov in nukleotidnih
zaporedij v genetiki. Nekaj več o tem bomo povedali v zadnjem razdelku.
Obzornik mat. fiz. 58 (2011) 4 133
Marko Razpet
Poravnava nizov
Prej povedano bomo sedaj posplošili. Iz črk, številk, ločil in morebitnih
drugih znakov nekega področja, ki ga obravnavamo, sestavimo množico A,
ki ji bomo rekli abeceda tega področja. Elementom abecede bomo rekli kar
znaki. V abecedo bomo dodali tudi znak za presledek, ki ga bomo označevali
z znakom  , da bo bolj viden. Niz ali beseda dolžine m je končno zaporedje
σ = a1a2 . . . am, kjer je vsak ak ∈ A, z izrazom prava beseda pa bomo
imenovali niz, v katerem ni znaka za presledek. Tudi v naravnem jeziku
namreč v besedah med črkami ni znaka za presledek. Niz σ = a1a2 . . . am je
torej prava beseda, če je v njej vsak ak ∈ A \ { }. Pametno je vpeljati tudi
znak za prazen niz : ⋄. Dolžino niza σ označimo z |σ|. Za σ = a1a2 . . . am
je torej |σ| = m. Katero koli nenegativno celo število m je zato lahko
dolžina nekega niza. Tako je na primer |⋄| = 0, |  | = 2, |RAKETA| = 6 in
|RAK ETA| = 7.
Pravi besedi
σ = a1a2 . . . am , τ = b1b2 . . . bn
poravnamo v enako dolga niza σ′ in τ ′ z dodajanjem znaka  tako, da znaki
ostanejo v istem vrstnem redu, znak  pa ne sme biti v σ′ in τ ′ hkrati na isti
poziciji. Če bi dovolili nasprotno, bi lahko dobili s poravnavo nize poljubne
dolžine s poljubno mnogo presledki. Vzemimo, da sta niza po poravnavi
dolžine ℓ:
σ′ = a′1a
′
2 . . . a
′
ℓ , τ
′ = b′1b
′
2 . . . b
′
ℓ .
Pri tem je a′k eden od ai ali  , b
′
k eden od bi ali  , za noben k pa ni a
′
k =
b′k =  , števila m,n, ℓ pa očitno povezuje relacija max(m,n) ≤ ℓ ≤ m + n.
Za prikaz poravnave je najbolje, da niza pǐsemo drugega nad drugim.
Navedimo nekaj poravnav različnih dolžin besed OBZORNIK in MATEMATIKA:
OB  ZORNIK OB  ZORNIK OB Z OR N IK  O BZO RNIK 
MATEMATIKA  MATEMATIKA   MATEMA TIKA MAT EMAT IKA
Poravnavo pravih besed σ in τ imamo lahko tudi za pretvorbo besede σ
v besedo τ ali obratno s tremi transformacijami nad njunimi znaki, in sicer
z brisanjem, vrivanjem in zamenjavo (vključujoč ohranjanje).
Ena od poravnav besed AKSIOM in VZROK dolžine 8 je
AKSI OM 
 V ZRO K
134 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
V tem primeru smo po vrsti uporabili naslednjih 8 transformacij:
1. brisanje znaka A;
2. zamenjavo znaka K z znakom V;
3. brisanje znaka S;
4. zamenjavo znaka I z znakom Z;
5. vrivanje znaka R;
6. ohranjanje znaka O;
7. brisanje znaka M;
8. vrivanje znaka K.
Po poravnavi dobljena niza spet stisnemo z opustitvijo presledkov:
AKSI OM 7→ AKSIOM,  V ZRO K 7→ VZROK.
V tem smislu smo prek poravnave besed z brisanjem, vrivanjem in za-
menjavo znakov pretvorili eno besedo v drugo. Podobno lahko opǐsemo tudi
obratno transformacijo, to je pretvorbo besede VZROK v besedo AKSIOM.
Poravnavo besed lahko vpeljemo tudi drugače. Iz abecede A konstrui-
ramo abecedo B = A×A. Znake nove abecede B označimo v obliki stolpca:
[
a
b
]
∈ B ⇐⇒ a ∈ A in b ∈ A .
Posebej označimo znak za presledek  v B:
 ∈ B ⇐⇒  =
[
 
 
]
.
Prave besede v B so po našem dogovoru končni nizi elementov iz B \ { }.
Iz dvojice pravih besed σ = a1a2 . . . am in τ = b1b2 . . . bn sestavimo novo
besedo dolžine ℓ z znaki abecede B takole:
[
a′1
b′1
][
a′2
b′2
]
. . .
[
a′ℓ
b′ℓ
]
. (1)
Prve koordinate stolpcev so znaki besede σ ali pa  . Podobno so druge
koordinate znaki besede τ ali  . Pri tem je vrstni red znakov brez  v novih
nizih enak kot v prvotnih nizih. Nikjer v nizu pa ne sme biti  nad  . Če
spregledamo oklepaje, dobimo ravno poravnavo besed σ in τ . Torej pri tem
nastopajo stolpci treh oblik:
[
a′k
b′k
]
=
[
 
bi
]
,
[
a′k
b′k
]
=
[
aj
 
]
,
[
a′k
b′k
]
=
[
ai
bj
]
.
133–145 135
Marko Razpet
V poravnavi dolžine ℓ naj bo v število stolpcev prve vrste, h druge in d
tretje vrste. Veljajo torej relacije: v + h + d = ℓ, m + v = ℓ, n + h = ℓ. Iz
njih izrazimo:
d = m+ n− ℓ , h = ℓ− n , v = ℓ−m. (2)
Število vseh poravnav dolžine ℓ besed dolžine m in n označimo s Q(m,n, ℓ).
To število pa lahko zapǐsemo s trinomskim koeficientom. V besedi (1) je
namreč nanizanih ℓ stolpcev, od katerih je v prve, h druge in d tretje vrste.
Takih pa je toliko, na kolikor načinov lahko permutiramo ℓ reči, od katerih
je v prve, h druge in d tretje vrste, zato je
Q(m,n, ℓ) =
ℓ!
h!v!d!
=
(
ℓ
h, v, d
)
, h+ v + d = ℓ.
Z upoštevanjem izrazov (2) dobimo:
Q(m,n, ℓ) =
(
ℓ
n
)(
n
m+ n− ℓ
)
=
(
ℓ
m
)(
m
m+ n− ℓ
)
. (3)
Vseh možnih poravnav pa je
D(m,n) =
m+n
∑
ℓ=max(m,n)
Q(m,n, ℓ). (4)
V nadaljevanju bomo z N označevali množico vseh celih nenegativnih
števil, torej N = {0, 1, 2, 3, . . .}. Števila D(m,n) ((m,n) ∈ N × N) imenu-
jemo Delannoyjeva števila, ker se je z njimi prvi ukvarjal francoski matema-
tik in častnik Henri-Auguste Delannoy (1833–1915) v povezavi s številom
šahovskih iger. Več o tem manj znanem matematiku lahko preberemo v [1].
Delannoyjeva števila
Za nazorno ponazoritev poravnav pravih besed dolžin m in n si lahko po-
magamo z množico točk
M(m,n) = {(x, y) : x ∈ {0, 1, 2, . . . ,m}, y ∈ {0, 1, 2, . . . , n}} ⊂ N× N.
Vsaki poravnavi pravih besed pa lahko povratno enolično priredimo neko
pot, ki povezuje nekatere točke vM(m,n). Pri tem povežemo točki (0, 0) in
136 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
v v v v v v v
v v v v v v v
v v v v v v v
v v v v v v v
v v v v v v v
v v v v v v v
A K S I O M
V
Z
R
O
K
(0, 0)
(6, 5)
Slika 1. Delannoyjeva pot k poravnavi besed AKSIOM in VZROK iz primera.
(m,n) z neko usmerjeno potjo, pri čemer so dovoljeni samo koraki v smeri
vektorjev (1, 0), (0, 1), (1, 1) (horizontalni, vertikalni, diagonalni). Vsaka
taka pot je Delannoyjeva pot.
Do Delannoyjeve poti, ki ustreza poravnavi pravih besed, pridemo tako,
da dani poravnavi priredimo korake takole:
[
aj
 
]
←→ (1, 0),
[
 
bj
]
←→ (0, 1),
[
ai
bj
]
←→ (1, 1).
Ustrezajo brisanju, vrivanju in zamenjavi znakov pri pretvorbi ene besede
v drugo. Pri tem gremo v poravnavi dolžine ℓ od leve proti desni, ustrezno
Delannoyjevo pot pa pričnemo v (0, 0) ∈ M(m,n), sledimo poravnavam in
po ℓ korakih prispemo v (m,n) ∈ M(m,n). Poravnavi besed AKSIOM in
VZROK, ki smo jo navedli zgoraj, ustreza Delannoyjeva pot na sliki 1.
Zato je Q(m,n, ℓ) ravno število Delannoyjevih poti z ℓ koraki od (0, 0)
do (m,n). Taka pot ima h = ℓ − n horizontalnih, v = ℓ −m vertikalnih in
d = m + n − ℓ diagonalnih korakov. Število najdalǰsih Delannoyjevih poti,
ki imajo m+ n korakov, je
Q(m,n,m+ n) =
(
m+ n
m
)
=
(
m+ n
n
)
,
133–145 137
Marko Razpet
število najkraǰsih Delannoyjevih poti z max(m,n) koraki pa je
Q(m,n,max(m,n)) =
(
max(m,n)
min(m,n)
)
.
Število vseh Delannoyjevih poti od (0, 0) do (m,n) je ravno Delannoyjevo
število D(m,n).
Števila Q(m,n, ℓ) so simetrična za vsak ℓ ∈ N: Q(m,n, ℓ) = Q(n,m, ℓ).
Prav tako so tudi Delannoyjeva števila simetrična: D(m,n) = D(n,m).
Oboja števila pa imajo rekurzijo. Za števila Q(m,n, ℓ) pridemo do nje z
naslednjim razmislekom. Denimo, da smo v ℓ − 1 koraku prispeli iz točke
(0, 0) v eno izmed točk (m−1, n), (m,n−1), (m−1, n−1). Takih možnosti
je Q(m− 1, n, ℓ− 1) +Q(m,n− 1, ℓ− 1) +Q(m− 1, n− 1, ℓ− 1). Iz katere
koli od omenjenih točk pa je potreben samo še en korak, da prispemo v
točko (m,n). Zato za števila Q(m,n, ℓ) za vse ℓ ≥ 1, m ≥ 1 in n ≥ 1 velja
rekurzija
Q(m,n, ℓ) = Q(m− 1, n, ℓ− 1) +Q(m,n− 1, ℓ− 1) +Q(m− 1, n− 1, ℓ− 1)
pri robnih pogojih Q(0, n, ℓ) = δn,ℓ in Q(m, 0, ℓ) = δm,ℓ, kjer je δ znani
Kroneckerjev simbol. Posebej namreč za m > 0 pomeni Q(m, 0, ℓ) število
poravnav niza dolžine m in praznega niza ⋄. Poravnavo, in to dolžine m,
v tem primeru dobimo samo na en način, z brisanjem vseh znakov niza σ.
Zato je Q(m, 0,m) = 1. Analogno najdemo: Q(0, n, n) = 1. Prazen niz pa
poravnamo s praznim nizom tudi le na en način, zato je Q(0, 0, 0) = 1.
Vpeljimo za ℓ ∈ N množico parov
T (ℓ) = {(i, j) ∈ N× N, 0 ≤ i ≤ ℓ, 0 ≤ j ≤ ℓ, i+ j ≥ ℓ}.
Na tej množici so števila Q(m,n, ℓ) pozitivna, na N×N\T (ℓ) pa so enaka 0.
Zgled je tabela 3. V funkcionalni analizi bi rekli, da je T (ℓ) nosilec funkcije
(m,n) 7→ Q(m,n, ℓ). Pri danem ℓ velja zanimiva enakost
∑
(m,n)∈T (ℓ)
Q(m,n, ℓ) = 3ℓ,
ki jo dokažemo z metodo matematične indukcije glede na parameter ℓ in s
pravkar dokazano rekurzijo, ki jo imajo števila Q(m,n, ℓ).
Za Delannoyjeva številaD(m,n) pa velja za vsem ≥ 1 in n ≥ 1 rekurzija
D(m,n) = D(m− 1, n) +D(m,n− 1) +D(m− 1, n− 1) (5)
138 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
n ↑
8 1 17 145 833 3649 13073 40081 108545 265729
7 1 15 113 575 2241 7183 19825 48639 108545
6 1 13 85 377 1289 3653 8989 19825 40081
5 1 11 61 231 681 1683 3653 7183 13073
4 1 9 41 129 321 681 1289 2241 3649
3 1 7 25 63 129 231 377 575 833
2 1 5 13 25 41 61 85 113 145
1 1 3 5 7 9 11 13 15 17
0 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 m→
Tabela 1. Delannoyjeva števila D(m,n).
pri robnih pogojih D(m, 0) = D(0, n) = 1. Dokažemo jo bodisi iz rekurzije
za števila Q(m,n, ℓ) in z vsoto (4) ali pa neposredno z naslednjim premisle-
kom.
Denimo, da smo prispeli po Delannoyjevi poti iz točke (0, 0) v eno izmed
točk (m−1, n), (m,n−1), (m−1, n−1). Takih možnosti je seveda natančno
D(m− 1, n) +D(m,n− 1) +D(m− 1, n− 1). Iz katere koli od omenjenih
točk pa je potreben samo še en dovoljen korak, da prispemo v točko (m,n).
Zato za števila D(m,n) velja zgornja rekurzija, s pomočjo katere lahko hitro
izračunamo Delannoyjeva števila za majhne m in n (tabela 1).
Obstaja več zapisov števil D(m,n). S formulo (3) na primer dobimo
D(m,n) =
m+n
∑
ℓ=max(m,n)
(
ℓ
m
)(
m
m+ n− ℓ
)
=
m+n
∑
ℓ=max(m,n)
(
ℓ
n
)(
n
m+ n− ℓ
)
,
pa tudi
D(m,n) =
min(m,n)
∑
k=0
(
m
k
)(
n
k
)
2k . (6)
Slednjo lahko izpeljemo popolnoma kombinatorično. Vsaki Delannoyjevi
poti od (0, 0) do (m,n) namreč lahko povratno enolično priredimo neki niz
simbolov H,V,D, pri čemer le-ti po vrsti označujejo horizontalni, vertikalni
in diagonalni korak. Vzemimo v takem nizu na piko podniza K = HV ,
nekakšen levi ovinek ali koleno, in podniz D. Delannoyjevih poti, na katerih
133–145 139
Marko Razpet
se K ali D pojavita natanko k-krat, je ravno
(
m
k
)(
n
k
)
2k.
Prvi faktor pomeni število načinov, na katere lahko k-krat nastopi eden od
omenjenih podnizov po horizontali dolžine m, drugi faktor število načinov,
na katere lahko k-krat nastopi eden od omenjenih podnizov po vertikali
dolžine n, tretji faktor pa pove, da k-krat izbiramo med dvema podnizoma.
Število vseh Delannoyjevih poti potem dobimo kot rezultat seštevanja po
vseh možnih številih k.
Pri malo večjih m in n so števila D(m,n) zelo velika, na primer:
D(10, 10) = 8 097 453 , D(16, 24) = 85 275 509 086 721.
Zato je dobrodošla kakšna ocena. A. Raichev in M. C. Wilson sta v [3]
izpeljala asimptotično formulo
D(Nm,Nn) ∼
(
n
L−m
)Nn(
m
L− n
)Nm√
mn
2πNL(m+ n− L)2
za N →∞, kjer je L =
√
m2 + n2.
Preden končamo razdelek, si še oglejmo, kdaj so trinomski koeficienti
največji, in lep primer, v katerem se pojavijo Delannoyjeva števila, čeprav
ni neposredno povezan z Delannoyjevimi potmi.
Vemo, da binomski koeficienti z izbranim zgornjim indeksom n in spo-
dnjim indeksom k (n, k ∈ N) pri lihih n dosežejo dvakrat svojo največjo vre-
dnost, pri sodih pa enkrat. Trinomski koeficienti pa pri izbranem zgornjem
indeksu dosežejo svojo največjo vrednost enkrat ali trikrat. Za največjo
vrednost Qℓ trinomskega koeficienta
(
ℓ
i, j, k
)
=
ℓ!
i!j!k!
(i, j, k ≥ 0, i+ j + k = ℓ)
namreč dobimo izraz
Qℓ =
(
ℓ
⌊ ℓ3⌋, ⌊ ℓ+13 ⌋, ⌊ ℓ+23 ⌋
)
.
Razlikovati je treba tri možnosti glede na ostanek pri deljenju števila ℓ
s 3. Označimo z mℓ in nℓ tisti števili, pri katerih je Qℓ = Q(mℓ, nℓ, ℓ). V
tabeli 2 so zbrane vse možnosti.
140 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
ℓ mℓ nℓ Qℓ
3λ 2λ 2λ ℓ!
λ!3
2λ 2λ+ 1
3λ+ 1 2λ+ 1 2λ ℓ!
λ!2(λ+1)!
2λ+ 1 2λ+ 1
2λ+ 1 2λ+ 2
3λ+ 2 2λ+ 2 2λ+ 1 ℓ!
λ!(λ+1)!2
2λ+ 1 2λ+ 1
Tabela 2. Števila Qℓ so odvisna od oblike indeksa ℓ.
Da ne bi imeli napačnega vtisa, da smo Delannoyjeva števila vpeljali
zgolj zaradi štetja poravnav nizov in Delannoyjevih poti, povejmo, da se
pojavljajo še marsikje, o čemer pa lahko več izvemo v izčrpni obravnavi
[5]. Omenimo samo primer. Za vsako pozitivno celo število n in vsako
nenegativno celo število m je v množici
On(m) = {(x1, x2, . . . , xn) ∈ Zn : |x1|+ |x2|+ . . .+ |xn| ≤ m}
natančno D(m,n) točk. Podrobnosti najdemo na primer v [4].
n ↑
8 1 8 28 56 70 56 28 8 1
7 8 56 168 280 280 168 56 8
6 28 168 420 560 420 168 28
5 56 280 560 560 280 56
4 70 280 420 280 70
3 56 168 168 56
2 28 56 28
1 8 8
0 1
0 1 2 3 4 5 6 7 8 m→
Tabela 3. Števila Q(m,n, 8) na nosilcu T (8). Največja so v okvirčkih.
Vemo, da je Rn poln metrični prostor za normo ||(x1, x2, . . . , xn)|| = |x1|+ |x2|+ . . .+
|xn| in da so v tem prostoru zaprte krogle s sredǐsčem v točki (0, 0, . . . , 0) in s polmerom
r ≥ 0 množice
Kn(r) = {(x1, x2, . . . , xn) ∈ R
n : |x1|+ |x2|+ . . .+ |xn| ≤ r}.
133–145 141
Marko Razpet
Potemtakem množica On(m) vsebuje natanko vse točke s celoštevilskimi koordinatami
krogle Kn(m) in D(m,n) pove število teh točk.
Samo po sebi je zanimivo, kako poimenovati nekatere geometrijske objekte v prostoru
R
n. Za n = 1 imamo opravka kar z množico R, ki jo točka x1 = 0 razdeli na dva dela: na
pozitivna in negativna števila. Krogla K1(r) pa je kar daljica s krajǐsčema v točkah −r in
r. Za n = 2 koordinatni osi x1 = 0 in x2 = 0 razdelita ravnino R
2 na 4 kvadrante, krogla
K2(r) pa je običajni kvadrat z oglǐsči (±r, 0) in (0,±r). Za n = 3 koordinatne ravnine
x1 = 0, x2 = 0 in x3 = 0 razdelijo prostor R
3 na 8 oktantov, krogla K3(r) pa je oktaeder
z oglǐsči (±r, 0, 0), (0,±r, 0) in (0, 0,±r).
V splošnem primeru koordinatne hiperravnine x1 = 0, x2 = 0, . . . , xn = 0 razdelijo
prostor Rn na 2n delov, ortantov. Krogla Kn(r) pa je n-razsežno hipertelo z oglǐsči
(±r, 0, 0, . . . , 0), (0,±r, 0, . . . , 0), . . . , (0, 0, 0, . . . ,±r).
Imena za to hipertelo so različna. Po analogiji s primerom n = 3 mu pravijo n-razsežni
hiperoktaeder. V uporabi pa sta tudi imeni krǐzni politop in ortopleks. Za naravno število
m ima torej n-razsežni hiperoktaeder natanko D(m,n) celoštevilskih točk.
Levenštejnova razdalja
Videli smo, da vsaki poravnavi pravih besed σ = a1a2 . . . am in τ = b1b2 . . . bn
v niza σ′ = a′1a
′
2 . . . a
′
ℓ in τ
′ = b′1b
′
2 . . . b
′
ℓ ustreza neka Delannoyjeva pot med
točkami množice M(m,n) in obratno. Delu poravnave na j-tem mestu,
zapisane s stolpcem oblike
[
a′j
b′j
]
,
pa lahko določimo tudi kazen ali ceno c(j, σ′, τ ′). Ta kazen je pozitivna,
vzeli bomo kar 1, če sta komponenti različni, in 0 sicer. To se pravi:
c(j, σ′, τ ′) =
{
1 , če je a′j 6= b′j ,
0 , če je a′j = b
′
j .
Isto lahko zapǐsemo tudi z relacijo c(j, σ′, τ ′) = ν(a′j 6= b′j), pri čemer ν(I)
pomeni Boolovo vrednost (1 ali 0) izjave I. Celotno kazen ali ceno poravnave
pa definiramo kot
c(σ′, τ ′) =
ℓ
∑
j=1
c(j, σ′, τ ′).
Želimo pa si, da je c(σ′, τ ′) najmanǰsa. Najmanǰsa kazen poravnave be-
sed σ, τ je Levenštejnova razdalja dL(σ, τ) med njima. Poimenovana je po
Vladimirju Iosifoviču Levenštejnu, leta 1935 rojenem ruskem znanstveniku,
uveljavljenem na področju teorije informacij in kod za popravljanje napak.
Za vsako besedo σ je dL(σ, σ) = 0 in dL(σ, ⋄) = |σ|. Levenštejnova razdalja
142 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
med besedama pove najmanǰse število vrivanj, brisanj in zamenjav znakov,
ki so potrebni za poravnavo teh besed.
Od poravnav
AKSI OM AKSIOM
 V ZRO K VZR OK
.....=.. ....=.
ima prva kazen c = 7, druga pa najmanǰso, c = 5. Znaki pod poravnavo
povejo kazen: pika 1 kazensko točko, enačaj nobene. Zato je v našem pri-
meru dL(AKSIOM, VZROK) = 5. Enako kazen imajo lahko različne poravnave
istih besed.
Algoritem za iskanje Levenštejnove razdalje med nizoma najdemo v mar-
sikaterem viru s tega področja, v našem jeziku je lepo opisan v [6]. Zato
bomo zgolj navedli ta algoritem za iskanje razdalje dL(σ, τ) besed
σ = a1a2 . . . am , τ = b1b2 . . . bn,
ki nam da tudi Delannoyjevo pot ustrezne poravnave. Rešitev je lahko več.
Definiramo števila L(i, j), kjer je 0 ≤ i ≤ m in 0 ≤ j ≤ n. Najprej za
0 ≤ i ≤ m in 0 ≤ j ≤ n postavimo
L(i, 0) = i, L(0, j) = j. (7)
Nato računamo rekurzivno z relacijo
L(i, j) = min(L(i− 1, j) + 1, L(i, j − 1) + 1, L(i− 1, j − 1) + ν(ai 6= bj))
in na koncu dobimo dL(σ, τ) = L(m,n). Z uvedbo polkolobarja (R ∪
{∞},⊕,⊙), v katerem sta definirani operaciji ⊕ in ⊙ s formulama
x⊕ y = min(x, y) in x⊙ y = x+ y,
lahko zapǐsemo
L(i, j) = 1⊙L(i− 1, j)⊕ 1⊙L(i, j − 1)⊕ ν(ai 6= bj)⊙L(i− 1, j − 1), (8)
kar spominja na rekurzijo Delannoyjevih števil v obliki
D(i, j) = 1 ·D(i− 1, j) + 1 ·D(i, j − 1) + 1 ·D(i− 1, j − 1) .
S polkolobarjem (R ∪ {∞},⊕,⊙) se ukvarja tropska matematika, ki je
dobila ime po vremenskih lastnostih Brazilije, kjer jo je okrog leta 1990 ute-
meljila skupina francoskih in brazilskih matematikov kot samostojno teorijo.
133–145 143
Marko Razpet
R 6 5 4 4 3 2 3
E 5 4 3 3 2 2 3
T 4 3 3 2 1 2 3
S 3 2 2 1 2 3 4
I 2 1 1 2 3 4 5
S 1 0 1 2 3 4 5
0 1 2 3 4 5 6
S E S T R A
Tabela 4. Števila L(i, j).
Pogosto je s tem v zvezi omenjen matematik in informatik madžarskega rodu
Imre Simon (1943–2009). V tropsko matematiko spadata na primer tropska
geometrija in tropska algebra. Tropska matematika je pripravna tudi za
obravnavo nekaterih problemov kombinatorike in dinamičnega programira-
nja, kamor uvrščamo tudi prej opisano iskanje Levenštejnove razdalje med
nizoma.
Oglejmo si primer etimološko bližnjih besed SESTRA in SISTER. Z upo-
rabo robnih pogojev (7) in rekurzije (8) izpolnimo tabelo 4 števil L(i, j).
Torej je dL(SESTRA, SISTER) = L(6, 6) = 3. Od L(6, 6) naredimo obratno
Delannoyjevo pot do L(0, 0). Splošno: v levo, če je L(i − 1, j) < L(i, j);
navzdol, če je L(i, j−1) < L(i, j); diagonalno, če je L(i−1, j−1) ≤ L(i, j).
V našem primeru imamo dve rešitvi:
R 6 5 4 4 3 2 3
E 5 4 3 3 2 2 3
T 4 3 3 2 1 2 3
S 3 2 2 1 2 3 4
I 2 1 1 2 3 4 5
S 1 0 1 2 3 4 5
0 1 2 3 4 5 6
S E S T R A
R 6 5 4 4 3 2 3
E 5 4 3 3 2 2 3
T 4 3 3 2 1 2 3
S 3 2 2 1 2 3 4
I 2 1 1 2 3 4 5
S 1 0 1 2 3 4 5
0 1 2 3 4 5 6
S E S T R A
Tabela 5. Ustrezni Delannoyjevi poti sta naznačeni s števili v krepkem tisku.
Ustrezni poravnavi sta:
SESTRA SEST RA
SISTER SISTER 
=.==.. =.==.=.
144 Obzornik mat. fiz. 58 (2011) 4
Poravnava nizov in Delannoyjeva števila
Poravnava nizov in genetika
Že skoraj 70 let (od leta 1944, veliko o tem je v [7]) je znano, da so v vseh
živih organizmih razen v nekaterih virusih nosilke dednih informacij mole-
kule deoksiribonukleinske kisline (DNK). Molekulo DNK si predstavljamo
kot dvojno vijačnico, sestavljeno iz riboznih (sladkornih) in fosfatnih gra-
dnikov. Obe vijačnici pa prečno povezujejo pari dušikovih baz adenin (A),
citozin (C), gvanin (G) in timin (T). Vedno sta v komplementarnem paru:
adenin in timin ter citozin in gvanin. Molekulo DNK si lahko predstavljamo
tudi kot lestev, ki smo jo zvili okoli njene vzdolžne simetrale, klini lestve
pa so pari dušikovih baz. Tako zgradbo sta leta 1953 na podlagi svojih
in predhodnih raziskav drugih znanstvenikov predvidela molekularni biolog
in fizik F. H. Crick (1916–2004) in molekularni biolog J. D. Watson (ro-
jen leta 1928), ki sta leta 1962 skupaj s fizikom in molekularnim biologom
M. D. Wilkinsom (1916–2004) prejela Nobelovo nagrado za fiziologijo ali
medicino. Slednji je z rentgensko metodo potrdil predvidevanje prvih dveh.
Vzdolž izbrane vijačnice molekule DNK si sledijo dušikove baze v nekem
zaporedju, ki ga vedno beremo v dogovorjeni smeri, vzdolž preostale vijač-
nice pa v obratnem komplementarnem zaporedju. Zaporedje lahko obravna-
vamo kot niz znakov abecede {A,C,G, T, -}. Črtico - je smiselno pridružiti
abecedi, ker z njo v zaporedju označimo izbris ali delecijo posamezne baze.
V nizu baz je zakodiran dedni zapis organizma. Genetiki s posebnim postop-
kom pridejo do teh nizov, jih poravnavajo in primerjajo med sabo. Tako
ugotavljajo na primer evolucijsko sorodnost med organizmi, ki jim DNK
pripada.
Povezavo med številom poravnav nizov in Delannoyjevimi potmi ter upo-
rabo v genetiki obravnava veliko del, na primer [2].
LITERATURA
[1] C. Banderier, S. Schwer, Why Delannoy numbers?, Journal of Statistical Planning and
Inference 135 (11/2005), str. 40–54.
[2] L. Pachter, B. Sturmfels, The mathematics of phylogenomics, SIAM Review 49 (2007),
št. 1, str. 3–31.
[3] A. Raichev, M. C. Wilson, A new method for computing asymptotics of diagonal co-
efficients of multivariate generating functions, arXiv:math/0702595v1, 9 str.
[4] M. Razpet, Nekaj primerov kombinatoričnega preštevanja, Matematika v šoli 13
(2007), št. 1–2, str. 78–96.
[5] R. A. Sulanke, Objects counted by the Delannoy numbers, Journal of Integer Sequences
6 (2003), članek 03.1.5, 19 str.
[6] A. Taranenko, Razdalja med nizi, Presek 35 (2007/08), št. 1, str. 25–27.
[7] J. D. Watson, A. J. Berry, DNK – skrivnost življenja, Modrijan, Ljubljana, 2007.
133–145 145