DNA圖的研究

A Study of DNA Graphs

游舜婷(Shun-Ting Yu)

指導教授 ： 傅恆霖

國立交通大學/理學院/應用數學系暨研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00477

摘要

分子生物學主要是研究DNA 序列及蛋白質的結構。由於序列的特性及讀取序列受到長度的限制， 利用建構有向圖的數學模型可以有效地確定DNA 序列及研究蛋白質的結構。此有向圖是這樣建構的：將每個長度為k 的核甘酸當成點，對於兩點x,y，如果x 這點後i 段的核甘酸與y 這點前i 段的DNA 序列要一樣，則x,y 有一條有向邊(x,y)。我們將這類的圖稱作DNA 圖或DNA 標記圖。兩者的差別在於核甘酸是否有重複使用。在這篇論文中， 我們主要是針對點數較小的圖去刻劃DNA 圖的特性。

關鍵字

DNA圖 ； DNA標記圖

並列摘要

Molecular biology aims to study DNA and protein structure, that is the recognition of DNA primary structure. In order to do that, a mathematical model based on graph theory has been developed in recent years. Mainly, suitably defined digraphs are presented. A digraph built from the spectrum (a set of some k-long oligonucleotides) as follows: each oligonucleotide from the spectrum becomes a vertex, two vertices are connected by an arc if the i rightmost nucleotides of the first point overlap with the i leftmost nucleotides of the second one. We refer to these graphs as DNA graphs and DNA labelled graphs depending on whether the oligonucleotides used are distinct or not. In this thesis, we study the digraphs mentioned above and characterize DNA labelled graphs which are also DNA graphs, especially when the order (number of vertices) is small

並列關鍵字

DNA graphs ； DNA labelled graphs

參考文獻

some properties of DNA graphs. Discrete Appl. Math.,

[3] B. Jacek, F. Piotr, K. Marta and K. Daniel, On the

recognition of de Bruijn graphs and their induced

subgraphs. Discrete Math., 245: 81 − 92(2002).

of the nucleotide sequence of DNA using hybridization