计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
9期
269-273,310
,共6页
项泰宁%郭丹%王海平%胡学钢
項泰寧%郭丹%王海平%鬍學鋼
항태저%곽단%왕해평%호학강
解空间%分割%模式匹配%通配符
解空間%分割%模式匹配%通配符
해공간%분할%모식필배%통배부
Solution space%Partitioning%Pattern matching%Wildcard
随着生物信息学、信息检索等领域的发展,带有通配符和长度约束的模式匹配问题引起了广泛关注.该问题扩展了精确模式匹配问题,使匹配更加灵活,同时也增加了匹配的复杂性,极大地提高了非线性匹配算法的复杂度.求解该问题的匹配算法的效率与问题的解空间密切相关,而目前针对该问题的解空间及其特征尚缺乏系统的研究.鉴于此,描述了该问题的解空间,并分析了解空间的可分性.之后,提出解空间划分算法SPLIT,并分析了SPLIT的时间复杂性.实验部分以3个匹配算法为对照,在真实DNA数据集下,使用了5109组模式.实验结果表明,SPLIT不影响匹配解的结构,且可以有效降低非线性匹配算法的时间消耗.
隨著生物信息學、信息檢索等領域的髮展,帶有通配符和長度約束的模式匹配問題引起瞭廣汎關註.該問題擴展瞭精確模式匹配問題,使匹配更加靈活,同時也增加瞭匹配的複雜性,極大地提高瞭非線性匹配算法的複雜度.求解該問題的匹配算法的效率與問題的解空間密切相關,而目前針對該問題的解空間及其特徵尚缺乏繫統的研究.鑒于此,描述瞭該問題的解空間,併分析瞭解空間的可分性.之後,提齣解空間劃分算法SPLIT,併分析瞭SPLIT的時間複雜性.實驗部分以3箇匹配算法為對照,在真實DNA數據集下,使用瞭5109組模式.實驗結果錶明,SPLIT不影響匹配解的結構,且可以有效降低非線性匹配算法的時間消耗.
수착생물신식학、신식검색등영역적발전,대유통배부화장도약속적모식필배문제인기료엄범관주.해문제확전료정학모식필배문제,사필배경가령활,동시야증가료필배적복잡성,겁대지제고료비선성필배산법적복잡도.구해해문제적필배산법적효솔여문제적해공간밀절상관,이목전침대해문제적해공간급기특정상결핍계통적연구.감우차,묘술료해문제적해공간,병분석료해공간적가분성.지후,제출해공간화분산법SPLIT,병분석료SPLIT적시간복잡성.실험부분이3개필배산법위대조,재진실DNA수거집하,사용료5109조모식.실험결과표명,SPLIT불영향필배해적결구,차가이유효강저비선성필배산법적시간소모.
