计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2007年
35期
57-60
,共4页
生物信息学%单体型检测%参数化算法%单核苷酸多态性
生物信息學%單體型檢測%參數化算法%單覈苷痠多態性
생물신식학%단체형검측%삼수화산법%단핵감산다태성
单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题.根据片段数据的特点提出了一个时间复杂度为O(nk22k2+mlogm+mk1)的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数(通常小于10),k2为覆盖同一SNP位点的片段的最大数(通常不大于10).对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值.
單體型組裝MEC問題指如何利用箇體的DNA測序片斷數據,翻轉最少的SNP位點值以確定該箇體單體型的計算問題.根據片段數據的特點提齣瞭一箇時間複雜度為O(nk22k2+mlogm+mk1)的參數化算法,其中m為片段數,n為單體型的SNP位點數,k1為一箇片斷覆蓋的最大SNP位點數(通常小于10),k2為覆蓋同一SNP位點的片段的最大數(通常不大于10).對于實際DNA測序中的片段數據,即使m和n都相噹大,該算法也可以在較短的時間得到MEC問題的精確解,具有良好的可擴展性和較高的實用價值.
단체형조장MEC문제지여하이용개체적DNA측서편단수거,번전최소적SNP위점치이학정해개체단체형적계산문제.근거편단수거적특점제출료일개시간복잡도위O(nk22k2+mlogm+mk1)적삼수화산법,기중m위편단수,n위단체형적SNP위점수,k1위일개편단복개적최대SNP위점수(통상소우10),k2위복개동일SNP위점적편단적최대수(통상불대우10).대우실제DNA측서중적편단수거,즉사m화n도상당대,해산법야가이재교단적시간득도MEC문제적정학해,구유량호적가확전성화교고적실용개치.
