Złożoność sekwencji językowej
Złożoność sekwencji językowej (LC) jest miarą „bogactwa słownictwa” tekstu genetycznego w sekwencjach genów . Kiedy nukleotydów jest zapisywana jako tekst przy użyciu czteroliterowego alfabetu, można obliczyć powtarzalność tekstu, to znaczy powtórzenia jego N-gramów (słów), co służy jako miara złożoności sekwencji. Tak więc, im bardziej złożona sekwencja DNA , tym bogatsze jest jej słownictwo oligonukleotydowe , podczas gdy powtarzające się sekwencje mają stosunkowo mniejszą złożoność. Kolejne prace ulepszyły oryginalny algorytm opisany w Trifonov (1990), nie zmieniając istoty podejścia do złożoności językowej.
Znaczenie LC można lepiej zrozumieć, biorąc pod uwagę prezentację sekwencji jako drzewa wszystkich podsekwencji danej sekwencji. Najbardziej złożone sekwencje mają maksymalnie zrównoważone drzewa, podczas gdy miara nierównowagi lub asymetrii drzew służy jako miara złożoności . Liczba węzłów na poziomie drzewa i jest równa rzeczywistej wielkości słownictwa słów o długości i w danej sekwencji; liczba węzłów w najbardziej zrównoważonym drzewie, które odpowiada najbardziej złożonej sekwencji o długości N, na poziomie drzewa i wynosi albo 4 i lub N-i+1, w zależności od tego, która wartość jest mniejsza. Złożoność ( C ) fragmentu sekwencji (o długości RW) można bezpośrednio obliczyć jako iloczyn miar użycia słownictwa (U i ):
Użycie słownictwa dla oligomerów o danym rozmiarze i można zdefiniować jako stosunek rzeczywistego rozmiaru słownika danej sekwencji do maksymalnego możliwego rozmiaru słownika dla sekwencji o tej długości. Na przykład U2 dla sekwencji ACGGGAAGCTGATTCCA = 14/16, ponieważ zawiera ona 14 z 16 możliwych różnych dinukleotydów; U 3 dla tej samej sekwencji = 15/15 i U 4 = 14/14. Dla sekwencji ACACACACACACACACA, U1 = 1/2; U2 = 2/16 = 0,125, ponieważ ma proste słownictwo składające się tylko z dwóch dinukleotydów ; U 3 dla tej sekwencji = 2/15. k-krotek z rozważanymi k od dwóch do W, podczas gdy W zależy od RW. Dla wartości RW mniejszych niż 18 W jest równe 3; dla RW mniejszego niż 67, W jest równe 4; dla RW<260, W=5; dla RW<1029, W=6 i tak dalej. Wartość C zapewnia miarę złożoności sekwencji w zakresie 0<C<1 dla różnych fragmentów sekwencji DNA o danej długości. Ta formuła różni się od pierwotnej miary LC pod dwoma względami: sposobem obliczania użycia słownictwa U i oraz tym, że i nie mieści się w przedziale od 2 do N-1, ale tylko do W. To ograniczenie zakresu U I sprawia, że algorytm jest znacznie bardziej wydajny bez utraty mocy. Zastosowano inną zmodyfikowaną wersję, w której złożoność językową (LC) definiuje się jako stosunek liczby podłańcuchów o dowolnej długości obecnych w łańcuchu do maksymalnej możliwej liczby podłańcuchów. Maksymalne słownictwo dla słów o rozmiarach od 1 do m można obliczyć według prostego wzoru. To obliczenie złożoności analizy sekwencji można wykorzystać do wyszukiwania konserwowanych regionów między porównywanymi sekwencjami w celu wykrycia regionów o niskiej złożoności, w tym prostych powtórzeń sekwencji, niedoskonałych bezpośrednich lub odwróconych powtórzeń , polipuryny i polipirymidyny struktury trójniciowego DNA i struktury czteroniciowe (takie jak kwadrupleksy G ).