國立高雄大學圖資館 |

語系: 繁體中文

說明(常見問題)

圖資館首頁

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

池設計的容錯性和連續型群試的研究 = Error-correcting ...

國立高雄大學應用數學系碩士班

池設計的容錯性和連續型群試的研究 = Error-correcting pooling designs and group testing for consecutive positives

紀錄類型:	書目-語言資料,印刷品 : 單行本
並列題名:	Error-correcting pooling designs and group testing for consecutive positives
作者:	蔡一慈,
其他團體作者:	國立高雄大學
出版地:	[高雄市]
出版者:	撰者;
出版年:	2014[民103]
面頁冊數:	27面圖，表 : 30公分;
標題:	群試設計
標題:	Group testing
電子資源:	http://handle.ncl.edu.tw/11296/ndltd/08606465922534618627
附註:	參考書目：面19-21
附註:	103年12月16日公開
附註:	內容為英文
摘要註:	在傳統群試問題(classical group testing problem)中，一集合𝑁內共有𝑛個元素，每一元素的性質非正即負，已知在𝑁中最多有𝑑個正的元素，目標是利用一些測試將所有正的找出。解決傳統群試問題的其中一種演算法稱為池設計(pooling designs)，是利用已知訊息將所有測試設計完成後再進行測試，通常可以用二元矩陣表示。在許多生物技術的應用上，池設計是一種標準實驗工具，在進行生物應用方面測試上，有時得到的結果可能會有錯誤出現，因此便有了構造具有容錯性質矩陣的研究。有些構造具容錯性矩陣的方法是利用「包含關係」概念生成。近幾年，以「交集關係」構造二元矩陣的概念被提出，並且發現容錯性比利用包含關係構造的矩陣甚佳。在此篇論文中，我們討論兩種以包含關係所構造矩陣，分別由D’yachkov 等人 (2007)及Bai 等人 (2009)所提出；將其改以交集概念構造，並且分析其容錯性。連續型群試 (group testing for consecutive positives)為具有連續性質的群試模型，其研究動機在於DNA 序列相關的生物應用上。在一集合𝑁中共有 𝑛 個元素，所有元素依照某種規則按順序排成一列，且每一元素的性質非正即負，在𝑁中最多有𝑑 個正的元素連續出現。在本篇論文中，我們探討矩陣 (𝑘, 𝑚, 𝑛)-selectors 的變形，並應用至二階段演算法 (two-stage algorithm)中，研究利用二階段演算法解決連續型群試問題，得到一測驗次數上界為12log_2(⌈𝑛/𝑑⌉) + 14𝑒 + 3𝑑 且其解碼時間(decoding complexity) 為𝑂(𝑛/𝑑 log 𝑛/𝑑 + 𝑑)。 Pooling designs are standard experimental tools in many biotechnical applications. Many famous pooling designs have been constructed from mathematical structures by "containing relation". Recently, pooling designs constructed by "intersecting relation" have been proposed by Nan and Guo (2010) and Guo and Wang (2011). Constructing by intersecting relation provides much better error-tolerance capabilities. In this thesis, we study the error-tolerance capabilities of pooling designs constructed by intersecting relation from combinatorial structures proposed by D'yachkov et al. (2007) and Bai et al. (2009). Motivated by application to DNA sequencing, group testing for consecutive positives has been proposed by Balding and Torney(1997) and Colbourn (1999) where n items are linearly ordered and all up to d positive items are consecutive in the order. In this thesis, we study a variation of (k; m; n)-selectors and use this combinatorial object to design a two-stage algorithm for group testing of consecutive positives. Our algorithm takes at most 12log_2 \lceil n/d \rceil +14e + 3d tests to identify all positives and its decoding complexity is O(n/d log n/d + d).

池設計的容錯性和連續型群試的研究 = Error-correcting pooling designs and group testing for consecutive positives
蔡, 一慈

池設計的容錯性和連續型群試的研究 = Error-correcting pooling designs and group testing for consecutive positives / 蔡一慈撰 - [高雄市] : 撰者, 2014[民103]. - 27面 ; 圖，表 ; 30公分.
參考書目：面19-21103年12月16日公開內容為英文.
群試設計Group testing

池設計的容錯性和連續型群試的研究 = Error-correcting pooling designs and group testing for consecutive positives
LDR:04236nam0a2200301 450 001 430264
005 20170214092745.0
009 430264
010 0 $b 精裝
010 0 $b 平裝
100 $a 20170214d2014 k y0chiy05 b
101 1 $a eng $d chi $d eng
102 $a tw
105 $a ak am 000yy
200 1 $a 池設計的容錯性和連續型群試的研究 $d Error-correcting pooling designs and group testing for consecutive positives $z eng $f 蔡一慈撰
210 $a [高雄市] $c 撰者 $d 2014[民103]
215 0 $a 27面 $c 圖，表 $d 30公分
300 $a 參考書目：面19-21
300 $a 103年12月16日公開
300 $a 內容為英文
314 $a 指導教授：張惠蘭博士
328 $a 碩士論文--國立高雄大學應用數學系碩士班
330 $a 在傳統群試問題(classical group testing problem)中，一集合𝑁內共有𝑛個元素，每一元素的性質非正即負，已知在𝑁中最多有𝑑個正的元素，目標是利用一些測試將所有正的找出。解決傳統群試問題的其中一種演算法稱為池設計(pooling designs)，是利用已知訊息將所有測試設計完成後再進行測試，通常可以用二元矩陣表示。在許多生物技術的應用上，池設計是一種標準實驗工具，在進行生物應用方面測試上，有時得到的結果可能會有錯誤出現，因此便有了構造具有容錯性質矩陣的研究。有些構造具容錯性矩陣的方法是利用「包含關係」概念生成。近幾年，以「交集關係」構造二元矩陣的概念被提出，並且發現容錯性比利用包含關係構造的矩陣甚佳。在此篇論文中，我們討論兩種以包含關係所構造矩陣，分別由D’yachkov 等人 (2007)及Bai 等人 (2009)所提出；將其改以交集概念構造，並且分析其容錯性。連續型群試 (group testing for consecutive positives)為具有連續性質的群試模型，其研究動機在於DNA 序列相關的生物應用上。在一集合𝑁中共有 𝑛 個元素，所有元素依照某種規則按順序排成一列，且每一元素的性質非正即負，在𝑁中最多有𝑑 個正的元素連續出現。在本篇論文中，我們探討矩陣 (𝑘, 𝑚, 𝑛)-selectors 的變形，並應用至二階段演算法 (two-stage algorithm)中，研究利用二階段演算法解決連續型群試問題，得到一測驗次數上界為12log_2(⌈𝑛/𝑑⌉) + 14𝑒 + 3𝑑 且其解碼時間(decoding complexity) 為𝑂(𝑛/𝑑 log 𝑛/𝑑 + 𝑑)。 Pooling designs are standard experimental tools in many biotechnical applications. Many famous pooling designs have been constructed from mathematical structures by "containing relation". Recently, pooling designs constructed by "intersecting relation" have been proposed by Nan and Guo (2010) and Guo and Wang (2011). Constructing by intersecting relation provides much better error-tolerance capabilities. In this thesis, we study the error-tolerance capabilities of pooling designs constructed by intersecting relation from combinatorial structures proposed by D'yachkov et al. (2007) and Bai et al. (2009). Motivated by application to DNA sequencing, group testing for consecutive positives has been proposed by Balding and Torney(1997) and Colbourn (1999) where n items are linearly ordered and all up to d positive items are consecutive in the order. In this thesis, we study a variation of (k; m; n)-selectors and use this combinatorial object to design a two-stage algorithm for group testing of consecutive positives. Our algorithm takes at most 12log_2 \lceil n/d \rceil +14e + 3d tests to identify all positives and its decoding complexity is O(n/d log n/d + d).
510 1 $a Error-correcting pooling designs and group testing for consecutive positives $z eng
610 0 $a 群試設計 $a 池設計 $a 容錯性 $a 連續型
610 1 $a Group testing $a Pooling design $a Error-tolerance $a Consecutive positives
681 $a 008M/0019 $b 462101 4418 $v 2007年版
700 1 $a 蔡 $b 一慈 $4 撰 $3 673476
712 0 2 $a 國立高雄大學 $b 應用數學系碩士班 $3 166142
801 0 $a tw $b NUK $c 20141021 $g CCR
856 7 $z 電子資源 $2 http $u http://handle.ncl.edu.tw/11296/ndltd/08606465922534618627