跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/01 13:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳顧仁
研究生(外文):Gu Ren Chen
論文名稱:生物晶片之探針配置問題
論文名稱(外文):Probe Placement Problems on Biochip
指導教授:吳哲賢吳哲賢引用關係
指導教授(外文):Jer-Shyan Wu
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:63
中文關鍵詞:生物晶片探針配置問題基因演算法
外文關鍵詞:biochipprobe placement problemsgenetic algorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:173
  • 評分評分:
  • 下載下載:41
  • 收藏至我的研究室書目清單書目收藏:0
生物晶片的用途可針對大量基因組同時做檢測與分析,目前生物晶片製造過
程有點墨法與光罩蝕刻法兩種,光罩蝕刻法之光罩序列又分為非週期、週期同
步、以及週期非同步三大類。本論文主要針對,在光罩蝕刻法之週期性同步光罩
序列下,探討探針配置問題。
探針配置問題是利用邊界最短問題來評估好壞,目前相關研究有利用旅行員
推銷問題演算法,以及列磊晶配置演算法。針對探針配置問題,我們首先利用基
因演算法來求解;接著改良列磊晶配置演算法,提出隨機列交換配置演算法;最
後結合上述兩種方法,設計出基因式隨機列交換配置演算法。
根據實驗結果分析,我們提出之基因式隨機列交換演算法,利用邊界最短問
題來評估探針配置好壞,所得到的結果優於目前相關研究。執行時間方面,亦有
不錯的表現。
There are two kinds of spotted and photolithographic methods for biochip
manufacture process; the mask sequence of photolithographic includes three types:
non-periodic, periodically synchronous, and periodically asynchronous cases. The
thesis mainly focuses on probe placement problems with periodically synchronous
mask sequence of photolithographic.
Until now, related researches have proposed TSP(Traveling Salesmen Problem)
and row-epitaxial placement algorithms. In the thesis, we first make use of genetic
algorithms, and then derive random row-exchange algorithms, finally propose genetic
random row-exchange algorithms.
According to experimental results, genetic random row-exchange algorithms is
better than the past researches of measuring BMP(Border Minimization Problem).
目錄
中文摘要........................................................................................................................ I
英文摘要.......................................................................................................................II
誌 謝......................................................................................................................... III
目錄............................................................................................................................. IV
圖目錄........................................................................................................................VII
第一章 導論................................................................................................................1
1.1 生物晶片簡介...............................................................................................................................1
1.1.1 生物晶片的歷史...................................................................................................................2
1.1.2 生物晶片的發展...................................................................................................................3
1.2 生物晶片種類...............................................................................................................................4
1.2.1 微陣列晶片...........................................................................................................................4
1.2.2 微處理晶片...........................................................................................................................5
1.3 探針合成與配置問題...................................................................................................................6
1.3.1 探針合成問題.......................................................................................................................6
1.3.2 探針邊界最短問題...............................................................................................................9
1.4 探針配置問題.............................................................................................................................10
1.5 研究動機與目的......................................................................................................................... 11
第二章 探針配置問題................................................................................................12
2.1 探針配置問題下限值.................................................................................................................13
2.2 旅行員推銷問題路徑配置演算法.............................................................................................14
2.3 列磊晶配置演算法.....................................................................................................................16
2.3.1 磊晶配置演算法.................................................................................................................16
目錄 v
2.3.2 列磊晶配置演算法.............................................................................................................19
第三章 基因演算法....................................................................................................20
3.1 基因演算法的起源.....................................................................................................................20
3.2 演算法的步驟.............................................................................................................................21
3.2.1 初始族群..............................................................................................................................24
3.2.2 編碼方式..............................................................................................................................25
3.2.3 適應函數..............................................................................................................................27
3.2.4 複製過程..............................................................................................................................28
3.2.5 交配過程..............................................................................................................................30
3.2.6 突變過程..............................................................................................................................33
3.2.7 族群取代..............................................................................................................................34
3.2.8 結束搜尋..............................................................................................................................35
第四章 基因式探針配置演算法...............................................................................37
4.1 探針配置問題基因演算法.........................................................................................................37
4.1.1 初始狀態..............................................................................................................................38
4.1.2 複製過程..............................................................................................................................39
4.1.3 交配過程..............................................................................................................................40
4.1.4 突變過程..............................................................................................................................44
4.1.5 終止條件..............................................................................................................................45
4.2 探針配置問題隨機列交換配置演算法......................................................................................46
4.2.1 隨機列交換演算法..............................................................................................................46
4.3 探針配置問題基因式隨機列交換演算法.................................................................................48
4.3.1 初始設定..............................................................................................................................48
4.3.2 複製過程..............................................................................................................................49
目錄 vi
4.3.3 交配過程..............................................................................................................................50
4.4.4 突變過程..............................................................................................................................51
4.4.5 終止條件..............................................................................................................................52
4.4 實驗結果與分析.........................................................................................................................53
4.4.1 輸入格式設定......................................................................................................................53
4.4.2 探針配置問題之配置演算法比較......................................................................................55
第五章 結論................................................................................................................58
5.1 研究成果....................................................................................................................................58
5.2 未來研究方向.............................................................................................................................59
參考文獻......................................................................................................................60
[1]M. Chee, R. Yang, E. Hubbell, A. Berno, X. Huang, D. Stern, J. Winkler, D. Lockhart, M. Morris, and S. Fodor, “Accessing genetic information with high-density DNA arrays”, Science Vol. 274, no. 5287, pp. 610-614, 1996.
[2]R. Cho, M. Campbell, E. Winzeler, L. Steinmetz, A. Conway, L. Wodicka, T. Wolfsberg, A. Gabrielian, D. Landsman, D. Lockhart, and R. Davis, “A genome-wide transcriptional analysis of the mitotic cell cycle”, Molecular Cell, Vol. 2, pp. 65-73, 1998.
[3]W. Feldman and P. Pevzner, “Gray code masks for sequencing by hybridization”, Genomics, vol. 23, no. 1, pp. 233–235, 1994.
[4]S. Fodor, J. Read, M. Pirrung, L. Stryer, L. Tsai, and D. Solas, “Light-directed, spatially addressable parallel chemical synthesis”, Science, vol. 251, no. 4995, pp. 767–773, 1991.
[5]R. Guigó and D. Gusfield, Eds., “Algorithms Bioinformatics”, WABI , Vol. 2452, pp. 435-448, 2002.
[6]S. Hannenhalli, E. Hubbell, R. Lipshutz, and P. Pevzner, “Combinatorial algorithms for design of DNA arrays”, Chip Technology, Springer-Verlag, pp. 1-19, 2002.
[7]A. Kahng, I. I. M˘andoiu, P. Pevzner, S. Reda, and A. Zelikovsky, “Border length minimization in DNA array design”, in Proc. 2nd Int. Workshop, Vol. 2425, pp. 435-448, 2002.
[8]A. Kahng, I. I. M˘andoiu, P. Pevzner, S. Reda, and A. Zelikovsky, “Computer-Aided Optimization of DNA Array Design and Manufacturing”, IEEE Trans. Comput. Aided Des., Vol. 25, no. 2, pp. 305-320, 2006.
[9]S. Kasif, Z. Weng, A. Derti, R. Beigel, and C. DeLisi, “A computational framework for optimal masking in the synthesis of oligonucleotide microarrays”, Nucleic Acids Res., vol. 30, no. 20, pp. 1-6, 2002.
[10]R. Lipshutz, S. Fodor, T. Gingeras, and D. Lockhart, “High density synthetic oligonucleotide arrays”, Nat. Genet., vol. 21, no. 1, pp. 20–24, 1999.
[11]D. Lockhart, H Dong, M. Byrne, M. Follettie, M. Gallo, M. Chee, M. Mittmann, C. Wang, M. Kobayashi, H. Horton, and E. Brown, “Expression monitoring by hybridization to high density oligo-nucleotide arrays”, Nature Biotechnology, Vol. 14, pp. 1675-1680, 1996.
[12]Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs”, Third Edition. Springer, 1996.
[13]W. Miller, M. Vingron, S. Istrail, P. Pevzner, and M. Waterman, “Engineering a scalable placement heuristic for DNA probe arrays”, Proc. 7th Annu. Int. Conf. Research Computational Molecular Biology (RECOMB), pp. 148–156, 2003.
[14]P. Pevzner, “Computational Molecular Biology: An Algorithmic Approach”, The MIT Press instead, 2000.
[15]S. Singh-Gasson, R. Green, Y. Yue, C. Nelson, F. Blattner, M. Sussman, and F. Cerrina, “Maskless fabrication of light-directed oligonucleotide microarrays using a digital micromirror array”, Nature Biotechnology, Vol. 17, pp. 974-978, 1999.
[16]K. Shahookar and P. Mazumder, “VLSI cell placement techniques”, Comput. Surv., vol. 23, no. 2, pp. 143–220, 1991.
[17]A. Tolonen, D. Albeanu, J. Corbett, H. Handley, C. Henson, and P. Malik, “Optimized in situ construction of oligomers on an array surface”, Nucleic Acids Res., vol. 30, no. 20, pp. 1-5, 2002.
[18]D. Wang, J. Fan, C. Siao, A. Berno, P. Young, R. Sapolsky, G. Ghandour, N. Perkins, E. Winchester, J. Spencer, L. Kruglyak, L. Stein, L. Hsie, T. Topaloglou, E. Hubbell, E. Robinson, M. Mittmann, M. Morris, N. Shen, D. Kilburn, J. Rioux, C. Nusbaum, S. Rozen, T. Hudson, R. Lipshutz, M. Chee, and E. Lander, “Large-scale identification, mapping, and genotyping of single-nucleotide polymorphisms in the human genome”, Science Vol. 280, no. 5366, pp. 1077-1082, 1998.
[19]L. Wodicka, H. Dong, M. Mittmann, M. Ho, and D. Lockhart, “Genome-wide expression monitoring in saccharomyces cerevisiae”, Nature Biotechnology, Vol. 15, pp. 1359-1367, 1997.
[20]柳超毅, “利用混合模型對微陣列資料做分群變異數分析”, 國立交通大學, 統計研究所碩士論文, 92年.
[21]莊佳叡, “以不同統計方法比較生物微晶片資料之研究”, 國立成功大學, 統計研究所碩士論文, 92年.
[22]鄭銘杰, “生物晶片光罩最小邊界問題之最佳解演算法”, 中華大學, 資訊工程研究所碩士論文, 92年.
[23]林岳鋒, “大氣電漿系統表面改質技術及其於微流體生物晶片製程之應用”, 國立中山大學, 機械與機電工程研究所碩士論文, 93年.
[24]曾家彥, “離心力驅動微流體系統之流道設計與分析”, 中原大學, 機械工程研究所碩士論文, 94年.
[25]張媛鈞, “評估cDNA微陣列資料的normalization方法”, 國立成功大學, 統計研究所碩士論文, 94年.
[26] 顏勝茂, “利用基因演算法建構演化樹之分析”, 中華大學, 資訊工程研究所碩士論文, 93年.
[27] 陳昭吉, “應用遺傳基因演算法於晶圓製造廠之設施佈置問題”, 元智大學, 工業工程管理研究所碩士論文, 93年.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top