Подниз

У математици, подниз неког низа је нови низ који се добија од почетног брисањем неких елемената низа, без промене релативног редоследа преосталих елемената.

Формално, претпоставимо да је X скуп, и да је (a_k)_{k ∈ K} низ у X, где је K = {1, 2, 3, ..., n} ако је (a_k) коначан низ, а K = N ако је (a_k) бесконачан низ. Тада је подниз од (a_k) низ облика $(a_{n_{r}})$ где је (n_r) строго растући низ у скупу индекса K.

Пример

На пример,

$<B,C,D,G>$

је подниз од

$<A,C,B,D,E,G,C,E,D,B,G>$,

са одговарајућим низом индекса < 3, 7, 9, 11 >.

Ако су дата два низа X и Y, за низ G се каже да је заједнички подниз од X и Y, ако је G подниз и од X и од Y. На примр, ако је

$X=<A,C,B,D,E,G,C,E,D,B,G>$ и

$Y=<B,E,G,C,F,E,U,B,K>$

онда би заједнички подниз од X и Y могао да буде

$G=<B,E,E>$

Ово не би био њихов најдужи заједнички подниз, јер је G дужине 3, а постоји заједнички подниз < B, E, E, B >, дужине 4. Најдужи заједнички подниз од X и Y је < B, E, G, C, E, B >.

Примене

Поднизови имају примене у рачунарству, посебно у области биоинформатике, где се користе за упоређивање, анализирање и складиштење ДНК ланаца.

Узмимо два ланца ДНК, на пример:

ORG₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Поднизови се користе да одреде колико су слични ланци ДНК, коришћењем ДНК база: аденина, гуанина, цитозина и тимина.

Подниска и подниз

У рачунарству, ниска се обично користи као синоним за низ, али је важно имати у виду да подниска и подниз нису синоними. Подниске су узастопни делови ниске, док поднизови не морају да узимају искључиво узастопне елементе низа. Ово значи да је подниска ниске увек подниз ниске, али обратно не мора да важи.

Литература

• Овај чланак садржи у себи материјале из чланка подниз са сајта PlanetMath, који је лиценциран под ГЛСД.
• Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. стр. 4. ISBN 978-0-521-58519-4.