Evaluating the Structure Properties of DNA by Using the Spanning Tree Invariant of the Topological Markov Chain Model

應用拓樸馬可夫鏈模式展開樹不變量評估DNA序列之結構性質

10.6773/JRMS.200712.0053

謝俊逸(Jiunn-I Shieh)；李桂仁(Kuei-Jen Lee)；劉湘川(Hsiang-Chuan Liu)；曾杏園(Hsing-Yuan Tseng)

拓樸馬可夫鏈模式 ； 展開樹不變量 ； DNA序列 ； 緊密性 ； topological Markov chain model ； spanning tree invariant ； DNA sequence ； compactness

測驗統計年刊

15期_下（2007 / 12 / 01）

53 - 62

英文

這項研究是使用一個拓樸馬可夫鏈模式從完全的基因組的去氧核糖核酸(DNA)序列順序中評估其架構性能的標準。在這項研究過程當中，我們選取4個細菌︰Halobacterium sp. NRC-1、Haloarcula marismortui、Campylobacter jejuni及Streptomyces coelicolor A3(2)，並應用拓樸馬可夫鏈模式之展開樹不變量進行序列評估。我們使用一個馬可夫鏈模型，建立一種框架模式，並利用選取的四種細菌的DNA序列去進行評估，分析其架構性能的特性及標準。我們相信基於不變量生成樹原理，我們能從生成樹的不變量中評估出在完全的基因組DNA序列架構中的隨機性(randomness)和緊密性(compactness)，而藉此種方法發現耐鹽性細菌的DNA序列特性。

In this study, four bacteria: Halobacterium sp. NRC-1, Haloarcula marismortui, Campylobacter jejuni, and Streptomyces coelicolor A3 (2), were investigated using the spanning tree invariant. This study used a topological Markov chain model to establish a framework to evaluate the level of structural properties of DNA from the complete genomic DNA sequences. Based upon the spanning tree invariant, we can evaluate the randomness and compactness of the complete genomic structures. Briefly, we discuss the correlations between GC contents and the values of spanning tree invariants.

1. Baliga, N.S.,Bonneau, R.,Facciotti, M.T.,Pan, M.,Glusman, G.,Deutsch, E.W.,Shannon, P.,Chiu,Y.,Weng, R.S.,Gan,R.R.,Hung,P.,Date, S.V.,Marcotte, E.,Hood, L.,Ng, W.V.(2004).Genome sequence of Haloarcula marismortui: A halophilic archaeon from the Dead Sea.Genome Res,14,2221-2234.
2. Bentley, S. D.,Chater, K. F.,Cerdeno-Tarraga, A. M.,Challis, G. L.,Thomson, N. R.,James, K. D.,Harris, D. E.,Quail, M. A.,Kieser, H.,Harper, D.,Bateman, A,Brown, S.,Chandra, G.,Chen, C. W.,Collins, M.,Cronin, A.,Fraser, A.,Goble, A.,Hidalgo, J.,Hornsby, T.,Howarth, S.,Huang, C.-H.,Kieser, T.,Larke, L.,Murphy, L.,Oliver, K.,O`Neil, S.,Rabbinowitsch, E.,Rajandream, M.-A.,Rutherford, K.,Rutter, S.,Seeger, K.,Saunders, D.,Sharp, S.,Squares, R.,Squares, S.,Taylor, K.,Warren, T.,Wietzorrek, A.,Woodward, J.,Barrell, B. G.,Parkhill, J.,Hopwood, D. A.(2002).Complete genome sequence of the model actinomycete Streptomyces coelicolor A3(2).Nature,417,141-147.
3. Bu, D.,Zhao, Y.,Cai, L.,Xue, H.,Zhu, X.,Lu, H.,Zhang, J.,Sun, S.,Ling, L.,Zhang, N.,Li, G.,Chen, R.(2003).Topological structure analysis of the protein-protein interaction network in budding yeast.Nucleic Acids Res.,31,2443-2450.
4. Hillier, F. S.,Lieberman, G. J.(2005).Introduction to Operations Research.McGraw Hill.
5. Jarvis, J. P.,Shier, D. R.,TW(Eds.)(1999).Applied Mathematical Modeling: A Multidisciplinary Approach.CRC Press.
6. Kennedy, S. P.,Ng, W. V.,Salzberg, S. L.,Hood, L.,DasSarma, S.(2001).Understanding the adaptation of Halobacterium species NRC1 to its extreme environment through computational analysis of its genome sequence.Genome Res.,11,1641-1650.
7. Lind, D.,Marcus, B.(1995).An Introduction to Symbolic Dynamics and Coding.Cambridge:Cambridge University Press.
8. Lind, D.,Tuncel, S.(2001).A spanning tree invariant for Markov shifts.Codes, Systems, and Graphical Models, IMA Volume on Mathematics and its Applications,123,487-497.
9. Mohar, B.,Alavi, Y.,Charchand, G.,Ollermann,O. R.,Schwenk, A. J.(1991).The Laplacian Spectrum of Graphs.Graph Theory, Combinatorics, and Applications,2
10. Ng, W. V.,Kennedy, S. P.,Mahairas, G. G.,Berquist, B.,Pan, M.,Shukla, H. D.,Lasky, S. R.,Baliga, N. S.,Thorsson, V.,Sbrogna, J.,Swartzell, S.,Weir, D.,Hall, J.,Dahl, T. A.,Welti, R.,Goo, Y. A.,Leithauser, B.,Keller, K.,Cruz, R.,Danson, M. J.,Hough, D. W.,Maddocks, D. G.,Jablonski, P. E.,Krebs, M. P.,Angevine, C. M.,Dale, H.,Isenbarger, T. A.,Peck, R. F.,Pohlschroder, M.,Spudich, J. L.,Jung, K. H.,Alam, M.,Freitas, T.,Hou, S.,Daniels, C. J.,Dennis, P. P.,Omer, A. D.,Ebhardt, H.,Lowe, T. M.,Liang, P.,Riley, M.,Hood, L.,DasSarma, S.(2000).Genome sequence of Halobacterium species NRC-1.Proc. Natl. Acad. Sci,97,12476-12181.
11. Parkhill, J.,Wren, B. W.,Mungall, K.,Ketley, J. M.,Churcher, C.,Basham, D.,Chillingworth, T.,Davies, R. M.,Feltwell, T.,Holroyd, S.,Jagels, K.,Karlyshev, A.V.,Moule, S.,Pallen, M. J.,Penn, C. W.,Quail, M. A.,Rajandream, M. A.,Rutherford, K. M.,Vliet, A. H. M. V.,Whitehead, S.,Barrell, B. G.(2000).The genome sequence of the foodborne pathogen Campylobacter jejuni reveals hypervariable sequences.Nature,403,665-668.
12. Taha, H. A.(1997).Operations Research: An Introduction.Prentice Hall.
13. Xie, A.,Beerel, P. A.(1998).Efficient state classification of finite state Markov chains.IEEE Transactions on Computer-Aided Design,17(2),1334-1338.