언어 시퀀스의 복잡성

Linguistic sequence complexity

언어 배열 복잡도(LC)는 유전자 [1]배열에서 유전자 텍스트의 '어휘 풍부도'를 측정하는 것입니다.뉴클레오티드 시퀀스를 4글자 알파벳으로 텍스트로 쓰면 텍스트의 반복성, 즉 N그램(단어)의 반복성을 계산할 수 있어 시퀀스 복잡성의 척도가 된다.따라서 DNA 배열이 복잡할수록 올리고뉴클레오티드 어휘가 풍부해지는 반면, 반복 배열은 상대적으로 복잡도가 낮다.후속 연구는 언어적 복잡성 [2][3][4]접근법의 본질을 바꾸지 않고 트리포노프(1990)[1]에 기술된 원래의 알고리즘을 개선했다.

LC의 의미는 시퀀스를 주어진 시퀀스의 모든 후속 트리로 표시함으로써 더 잘 이해할 수 있다.가장 복잡한 시퀀스는 최대한 균형 잡힌 트리를 가지며, 불균형 또는 트리 비대칭의 측정은 복잡성 척도의 역할을 한다.트리 레벨의 노드 수는 주어진 시퀀스의 길이를 가진 단어의 실제 어휘 크기와 같습니다. 트리 레벨의 가장 복잡한 길이 N의 시퀀스에 대응하는 가장 균형 잡힌 트리 내의 노드 수는 4 또는 N-i+1 중 더i 작은 것입니다.시퀀스 단편(길이 RW)의 복잡도()C는 어휘 사용 척도(U)[2]의i 곱으로 직접 계산할 수 있다.

특정 크기의 올리고머에 대한 어휘 사용은 해당 길이의 배열에 대해 가능한 최대 어휘 크기에 대한 특정 배열의 실제 어휘 크기의 비율로 정의할 수 있다.예를2 들어 ACGGAGCTGATTCCA = 14/16 배열의 U는 16가지 가능한 다른 디뉴클레오티드 중 14가지를 포함하므로 동일3 배열의 U는 15/15, U4=14/14이다.ACACACACACACACACACACACA 배열의1 경우, U=1/2; U=2/16=0.125; 이23 배열의 경우 U=2/15. 고려된 k-tuples는 2에서 W까지이며, W는 RW에 의존한다.RW 값이 18보다 작을 경우 W는 3이고, 67보다 작을 경우 W는 4이며, RW가 260보다 작을 경우 W=5, RW가 1029보다 작을 경우 W=6과 같습니다.값은 특정 [2]길이의 다양한 DNA 배열 조각에 대해 0<C<1 범위의 배열 복잡성을 측정합니다.이 공식은 두 가지i 점에서 원래의 LC[1] 측정값과는 다릅니다.단어사용량 U의 계산방법과 2 ~N-1의 범위가 아니라 W까지의 범위이기 때문입니다.U 의 범위에i 대한 이러한 제한에 의해,[2] 전력의 손실 없이 알고리즘의 효율이 큰폭으로 향상됩니다.in은 다른 수정 버전을 사용했습니다.Languical Complexity(LC; 언어 복잡도)는 가능한 최대 서브스트링 수에 대한 문자열 길이의 서브스트링 수의 비율로 정의됩니다.단어 크기 1에서 m까지의 최대 어휘는 간단한 [5]공식에 따라 계산될 수 있습니다.이 배열 분석 복잡도 계산은 단순 배열 반복, 불완전한 직접 또는 반전 반복, 폴리푸린 및 폴리피리미딘 삼중사슬 DNA 구조, 4가닥 구조(G-quadruplexes 등)를 포함한 저복잡도 영역 검출을 위해 비교 배열 사이의 보존 영역을 탐색하는 데 사용될 수 있다.를 클릭합니다.[6]

레퍼런스

  1. ^ a b c Edward N. Trifonov (1990). "Making sense of the human genome". Structure and Methods, Vol. 1. Human Genome Initiative and DNA Recombination; Proceedings of the Sixth Conversation in the Discipline Biomolecular Stereodynamics. Albany, New York: Adenine Press. pp. 69–77.
  2. ^ a b c d Gabrielian, A. (1999). "Sequence complexity and DNA curvature". Computers & Chemistry. 23 (3–4): 263–274. doi:10.1016/S0097-8485(99)00007-8. PMID 10404619.
  3. ^ Orlov, Y. L.; Potapov, V. N. (2004). "Complexity: An internet resource for analysis of DNA sequence complexity". Nucleic Acids Research. 32 (Web Server issue): W628–W633. doi:10.1093/nar/gkh466. PMC 441604. PMID 15215465.
  4. ^ Janson, S.; Lonardi, S.; Szpankowski, W. (2004). "On average sequence complexity". Theoretical Computer Science. 326 (1–3): 213–227. doi:10.1016/j.tcs.2004.06.023.
  5. ^ a b Troyanskaya, O. G.; Arbell, O.; Koren, Y.; Landau, G. M.; Bolshoy, A. (2002). "Sequence complexity profiles of prokaryotic genomic sequences: A fast algorithm for calculating linguistic complexity". Bioinformatics. 18 (5): 679–88. doi:10.1093/bioinformatics/18.5.679. PMID 12050064.
  6. ^ Kalendar, R.; Lee, D.; Schulman, A. H. (2011). "Java web tools for PCR, in silico PCR, and oligonucleotide assembly and analysis". Genomics. 98 (2): 137–144. doi:10.1016/j.ygeno.2011.04.009. PMID 21569836.