计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2011年
11期
184-186,189
,共4页
陈聪%韩建民%贾泂%辛德东
陳聰%韓建民%賈泂%辛德東
진총%한건민%가형%신덕동
有限状态自动机%DNA子序列%重复体频率%频率统计算法%最长公共子序列
有限狀態自動機%DNA子序列%重複體頻率%頻率統計算法%最長公共子序列
유한상태자동궤%DNA자서렬%중복체빈솔%빈솔통계산법%최장공공자서렬
针对现有DNA重复体频率统计算法效率低、灵活性差等不足,基于字符串多模式匹配的有限状态自动机,构造DNA子序列比对自动机,利用KMP算法对自动机进行状态转移优化,由此提出一种高效的重复体频率统计算法.该算法通过对DNA数据库的线性扫描,得到每个DNA子序列在全局数据库中重叠与非重叠的重复体频率统计信息以及指定DNA序列集合的最长公共子序列信息.实验结果表明,该算法具有效率高、匹配精确、信息获取方式灵活、支持在线操作等优势.
針對現有DNA重複體頻率統計算法效率低、靈活性差等不足,基于字符串多模式匹配的有限狀態自動機,構造DNA子序列比對自動機,利用KMP算法對自動機進行狀態轉移優化,由此提齣一種高效的重複體頻率統計算法.該算法通過對DNA數據庫的線性掃描,得到每箇DNA子序列在全跼數據庫中重疊與非重疊的重複體頻率統計信息以及指定DNA序列集閤的最長公共子序列信息.實驗結果錶明,該算法具有效率高、匹配精確、信息穫取方式靈活、支持在線操作等優勢.
침대현유DNA중복체빈솔통계산법효솔저、령활성차등불족,기우자부천다모식필배적유한상태자동궤,구조DNA자서렬비대자동궤,이용KMP산법대자동궤진행상태전이우화,유차제출일충고효적중복체빈솔통계산법.해산법통과대DNA수거고적선성소묘,득도매개DNA자서렬재전국수거고중중첩여비중첩적중복체빈솔통계신식이급지정DNA서렬집합적최장공공자서렬신식.실험결과표명,해산법구유효솔고、필배정학、신식획취방식령활、지지재선조작등우세.
