计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2015年
4期
244-248
,共5页
模式匹配%通配符%剪枝%约束
模式匹配%通配符%剪枝%約束
모식필배%통배부%전지%약속
Pattern matching%Wildcard%Pruning%Constraints
近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.
近年來,隨著生物信息學、信息檢索等領域的髮展,串模式匹配問題被不斷擴展.其中,具有代錶性的是在模式中引入可變長度的通配符而形成帶有通配符的模式匹配(PMWL).該問題定義的靈活性給用戶提供瞭方便,卻也造成瞭求解上的睏難.因此,如何在多項式時間內得到更好的匹配解成為研究的焦點.提齣瞭一種啟髮式的小兵算法.小兵算法通過將PMWL問題轉化為路徑搜索問題,併藉鑒動態剪枝思想,在算法搜索的過程中動態地將不可能的匹配位置剪枝,從而提高解的質量.實驗在真實DNA序列上進行,併人工生成瞭196箇模式.結果錶明,相比于目前最有效的SAIL算法,小兵算法在絕大多數的尾部有重複字符的模式中可以穫得更好的匹配解.
근년래,수착생물신식학、신식검색등영역적발전,천모식필배문제피불단확전.기중,구유대표성적시재모식중인입가변장도적통배부이형성대유통배부적모식필배(PMWL).해문제정의적령활성급용호제공료방편,각야조성료구해상적곤난.인차,여하재다항식시간내득도경호적필배해성위연구적초점.제출료일충계발식적소병산법.소병산법통과장PMWL문제전화위로경수색문제,병차감동태전지사상,재산법수색적과정중동태지장불가능적필배위치전지,종이제고해적질량.실험재진실DNA서렬상진행,병인공생성료196개모식.결과표명,상비우목전최유효적SAIL산법,소병산법재절대다수적미부유중복자부적모식중가이획득경호적필배해.
