华中科技大学学报（自然科学版）
華中科技大學學報（自然科學版）
화중과기대학학보（자연과학판）
JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURE SCIENCE)
2005年
z1期
265-267
,共3页
DNA序列%字符串%图案匹配%Boyer-Moore算法
DNA序列%字符串%圖案匹配%Boyer-Moore算法
DNA서렬%자부천%도안필배%Boyer-Moore산법
通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ+m),其中σ和m分别为字母表的大小和字符串图案的长度.采用真实的人类DNA序列测试,包括序列库中前1 000个长度超过1 000的完整序列作为文本,从中随机选出1 000个长度为20的序列片段作为图案,进行实验对比,证明可以将搜索时间平均缩短到原来的约90%.
通過理論分析和測試髮現,對大多數字符串而言,按某箇方嚮搜索文本總是會比按另一箇方嚮的搜索速度快.提齣瞭新的預處理算法,在使用Boyer-Moore算法之前先確定一箇較優的搜索方嚮,其時間複雜度和空間複雜度分彆為O(σm)和O(σ+m),其中σ和m分彆為字母錶的大小和字符串圖案的長度.採用真實的人類DNA序列測試,包括序列庫中前1 000箇長度超過1 000的完整序列作為文本,從中隨機選齣1 000箇長度為20的序列片段作為圖案,進行實驗對比,證明可以將搜索時間平均縮短到原來的約90%.
통과이론분석화측시발현,대대다수자부천이언,안모개방향수색문본총시회비안령일개방향적수색속도쾌.제출료신적예처리산법,재사용Boyer-Moore산법지전선학정일개교우적수색방향,기시간복잡도화공간복잡도분별위O(σm)화O(σ+m),기중σ화m분별위자모표적대소화자부천도안적장도.채용진실적인류DNA서렬측시,포괄서렬고중전1 000개장도초과1 000적완정서렬작위문본,종중수궤선출1 000개장도위20적서렬편단작위도안,진행실험대비,증명가이장수색시간평균축단도원래적약90%.
