DNA 重複片段的樣式與DNA 定序機率之研究

THE STUDY ON THE PATTERNS OF DNA REPEATS AND THE PROBABILITY OF DNA SEQUENCING

蔡佩芳(Pei-Fang Tsai)

指導教授 ： 張薰文

大同大學/電機資訊學院/應用數學學系所/碩士(2004年)

摘要

DNA 分子已經被證實是一種遺傳物質，其特性可由四種鹽基：A、
C、G 和T 的順序所決定的。因此，DNA 定序已成為計算分子生物學中
的重要課題之一。然而在DNA 定序的過程中，重複片段的出現將使得
DNA定序變得更加複雜，並且可能造成原始DNA無法被重建。由於DNA
定序機率與重複片段的樣式有關，因此在本篇論文中，我們研究DNA
重複片段的樣式，與DNA 定序機率之間的關係。
我們首先以雜交定序法得到DNA 序列中的所有子序列為基礎，建
構出一個簡化的有向圖，圖中的每一頂點代表不同的重複片段，則圖中
每一個尤拉圈皆可導出一個可能的重建。因此，DNA 定序的機率可藉由
計算尤拉圈的數目來獲得。在另一方面，我們介紹DNA 的樣式圖，使
得DNA 重複片段的樣式可以簡明地表示。基於組合理論的概念，我們
特性化會導致k 個可能定序的DNA 重複片段之樣式，並計算相關樣式
的個數，及其生成函數。最後，我們針對特定的重複樣式進行延伸性討
論，並提出相關結果。

關鍵字

DNA定序，雜交定序，重複片段，簡化的有向圖，重複片段樣式圖，Catalan數，生成函數，遞迴關係式。

並列摘要

DNA molecules have been proved be the generic material, and their properties are
determined by the order of four kinds of bases: A , C , G , and T . Hence DNA
sequencing has become one of important topics in the computational molecular biology.
In DNA sequencing, the occurrence of repeats will complicate DNA sequencing and may
prevent from the unique reconstruction. Moreover, the probability of DNA sequencing
depends on the patterns of DNA repeats. In this thesis, we study the relationship
between the patterns of DNA repeats and the probability of DNA sequencing.
After sequencing by hybridization, a simple set, called spectrum, of all fixed-
length subsequences in target DNA is obtained. Based on the spectrum, we construct a
reduced digraph where each vertex represents a distinct repeat. Then each Euler circuit
in the reduced digraph may result in a possible reconstruction. Hence the probability of
DNA sequencing can be obtained by evaluating the number of Euler circuits. On the
other hand, we introduce pattern graphs that are easy to present the patterns of DNA
repeats. Based on the combinatorial concepts, we characterize the patterns of DNA
repeats of k possible reconstructions for some specific k s. Moreover, we enumerate
the patterns of DNA repeats that have k possible sequencings, and find the
corresponding generating functions. Finally, we do some extended studies and present
related results for specific repetitive patterns.

並列關鍵字

Catalan number ； Deduced digraph ； DNA sequencing ； generating function ； pattern graph of repeats ； recurrence relation. ； Repeats ； Sequencing by hybridization

參考文獻

and sequencing by hybridization, Discrete Applied Mathematics 104 (2000)

63-96.

DNA graphs, Discrete Applied Mathematics 98 (1999) 1-19.

Bruijn graphs and their induced subgraphs, Discrete Mathematics 245 (2002)

81-92.