De bruijn secvenţă

O secvență de Bruijn [1] este o ordine ciclică ale cărei elemente aparțin unei mulțimi finite date (mulțimea este de obicei considerată ), astfel încât toate subsecvențele sale [2] de o lungime dată sunt distincte. $a_{1},\;\ldots ,\;a_{t}$ $\{0,\;1,\;\ldots ,\;k-1\}$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $n$

Sunt adesea luate în considerare secvențe periodice cu punct , care conțin diferite subsecvențe , adică astfel de secvențe periodice în care orice segment de lungime este o secvență de Bruijn cu aceiași parametri și . $T$ $T$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $T+n-1$ $n$ $k$

Ciclurile poartă numele matematicianului olandez Nicholas de Bruijn , care le-a studiat în 1946 [3] , deși au mai fost studiate [4] .

Proprietăți

În mod evident, lungimea (perioada) unui astfel de ciclu nu poate depăși - numărul tuturor vectorilor de lungime diferiți cu elemente din ; Este ușor de demonstrat că această estimare este atinsă. Ciclurile cu această lungime maximă posibilă sunt de obicei numite cicluri de Bruijn (cu toate acestea, uneori, acest termen este aplicat și la ciclurile de lungime mai scurtă). $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$

Pentru , există astfel de cicluri de Bruijn cu o lungime cu unu mai mică decât maximul, care sunt exprimate prin relații de recurență liniare de ordin Pe baza unor astfel de secvențe, în special, este construit codul ciclic redundant CRC32 (EDB88320). $k=2$ $n$ $n=3$ $x_{n}=x_{{n-2}}+x_{{n-3}}{\pmod 2}$

Exemple

Exemple de cicluri de Bruijn pentru perioadele 2, 4, 8, 16: $k=2$

01 (conține subsecvențele 0 și 1)
0011 (conține subsecvențele 00, 01, 11, 10)
00010111 (000, 001, 010, 101, 011, 111, 110, 100)
0000100110101111

Numărul de cicluri de Bruijn

Numărul de cicluri de Bruijn cu parametri este de asemenea ( un caz special al teoremei lui de Bruijn este teorema BEST , numită după numele lui de Bruijn, Tatiana Ehrenfest , Cedric Smith și William Tutt ). $n$ $k$ $k!^{{k^{{(n-1)}}}}/k^{n}$

Comte de Bruyne

Există o interpretare convenabilă a secvențelor și ciclurilor de Bruijn bazată pe așa-numitul graf de Bruijn — un grafic direcționat cu vârfuri corespunzătoare diferitelor seturi de lungimi cu elemente din , în care o muchie duce de la vârf la vârf dacă și numai dacă ( ); în acest caz, muchia în sine poate fi asociată cu un set de lungimi : . Pentru un astfel de grafic, căile Euler ( cicluri euleriene ) care nu trec de două ori prin aceeași muchie corespund unei secvențe (ciclu) de Bruijn cu parametri și , iar căile hamiltoniene ( cicluri hamiltoniene ) care nu trec de două ori prin același vârf corespund. la o secvenţă (ciclu) de Bruijn cu parametrii şi . $k^{n}$ $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$ $(x_{1},\;\ldots ,\;x_{n})$ $(y_{1},\;\ldots ,\;y_{n})$ $x_{i}=y_{{i-1}}$ $i=2,\;\ldots ,\;n$ $n+1$ $(x_{1},\;\ldots ,\;x_{n},\;y_{n})=(x_{1},\;y_{1},\;\ldots ,\;y_{n} )$ $n+1$ $k$ $n$ $k$

Graficul de Bruijn este utilizat pe scară largă în bioinformatică în sarcinile de asamblare a genomului .

Note

↑ Există și ortografii „de Bruyn” și „de Bruyn”.
↑ Dacă , atunci elementul cu index este selectat într-o ordine ciclică $j>t$ $j{\bmod {t)}$
↑ de Bruijn NG O problemă combinatorie // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. - v. 49.-pp. 758-764.
↑ Flye Sainte-Marie C. Întrebarea 48 // L'intermédiaire math. - 1894. - v. 1.-pp. 107-110.

Secvențe și rânduri
Secvențe	Succesiunea numerică Secvență fundamentală Secvență liniară recurentă numerele Fibonacci numere ondulate Factorială secvența Barker de bruijn secvenţă
Rânduri, de bază	Suma rândurilor Restul rândului Convergență condiționată Serii alternante Rând multisecțiune
Seria de numere ( operații cu seria de numere )	serie armonică seria Leibniz O serie de pătrate inverse O serie de numere prime reciproce rândul Dirichlet Seria Mercator Row Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
rânduri funcționale	Seria Taylor Seria Laurent Seria Fourier Seria Fourier trigonometrică serie trigonometrică Seria Wiener
Alte tipuri de rânduri	Seria Neumann rândul Puiseux