重建二倍體個(gè)體單體型的改進(jìn)環(huán)基算法
摘要:Hap Compass算法是求解最少帶權(quán)邊刪除模型(the minimum weighted edge removal,MWER)的有效啟發(fā)式方法,該算法采用刪除權(quán)值絕對(duì)值最小的邊的方式消除沖突環(huán)基,當(dāng)同時(shí)存在多條權(quán)值絕對(duì)值最小的邊時(shí),HapCompass隨機(jī)選擇刪除邊,導(dǎo)致求解方案的不確定性,降低重建效果。針對(duì)該問題,提出IHap Compass算法,改進(jìn)去邊規(guī)則,利用00 11 和01 10分型的片段支持差異數(shù)與總片段數(shù)之間的比值來確定刪除邊,對(duì)隨機(jī)取值問題做出有效限定。此外,IHap Compass以單體型中0/1取值的概率為圖中孤立點(diǎn)賦值,明確孤立點(diǎn)取值。采用真實(shí)單體型數(shù)據(jù)進(jìn)行測試,結(jié)果表明,IHap Compass算法在各種參數(shù)設(shè)置下,均能獲得較算法Hap Compass、DGS和Fast Hare更高的單體型重建率,具有較高的執(zhí)行效率。該算法為求解二倍體個(gè)體單體型重建問題提供一定的參考。
注: 保護(hù)知識(shí)產(chǎn)權(quán),如需閱讀全文請(qǐng)聯(lián)系山東工業(yè)大學(xué)學(xué)報(bào)雜志社