《基於圖論方法的DNA序列編碼研究》是依託北京大學，由朱恩強擔任負責人的面上項目。
基本介紹
- 中文名：基於圖論方法的DNA序列編碼研究
- 項目負責人：朱恩強
- 項目類別：面上項目
- 依託單位：北京大學
項目摘要,結題摘要,
項目摘要
在基因工程，特別是生物計算機的研製過程中，DNA編碼理論和設計方法是關鍵。特異性雜交和解鏈溫度，特別是鏈短且編碼序列多這一矛盾的需求，使得DNA編碼設計非常困難，並已被證明是NP-完全的問題。編碼問題旨在尋找滿足不與自身或其補序列互相交叉雜交的最大的DNA單鏈的集合，可以描述成一個組合最佳化問題。 因此，本項目擬有機地將DNA編碼與圖論方法，包括圖的獨立集理論，圖著色理論，圖的連通性理論等結合，力爭建立一套完整的精準的DNA編碼體系。本項目的研究內容主要分為以下4個方面： (1) 提出雜交距離的方法用來衡量DNA序列之間的相似度；(2) 將編碼問題轉化成圖的獨立集問題來尋找滿足不同約束條件下的最大編碼集合；(3) 設計在編碼長度，GC含量，雜交距離，值和特異性雜交這五種約束條件下的DNA編碼方法；(4) 研發編碼相應的軟體並給出套用。
結題摘要
DNA編碼設計在生物計算機的研製過程中至關重要。在實際設計中，DNA編碼會受到多種因素的影響和制約，如特異性雜交、解鏈溫度、鏈短且編碼序列多等，從而使得DNA編碼非常困難，該問題已被證明是NP-完全的。編碼問題旨在尋找滿足不與自身或其補序列互相交叉雜交的最大的DNA單鏈的集合，可以描述成一個組合最佳化問題。 為此，本項目通過研究圖的獨立集，圖的鄰點著色和無圈著色以及圖的連通性等多種組合最佳化問題，得到用於求解DNA編碼問題的若干算法和理論。此研究為進一步建立完整的DNA編碼體系提供了理論依據和指導。
