计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2006年
z3期
195-199
,共5页
王镝%王国仁%吴青泉%陈白尘%赵毅%毛克明
王鏑%王國仁%吳青泉%陳白塵%趙毅%毛剋明
왕적%왕국인%오청천%진백진%조의%모극명
DNA序列%重复片段%LPR%模式单元%后继数组
DNA序列%重複片段%LPR%模式單元%後繼數組
DNA서렬%중복편단%LPR%모식단원%후계수조
DNA序列中的重复片段在人类基因研究中有着非常重要的生物意义,因此,查找给定DNA序列中的重复片段是生物序列分析领域中的一个重要课题.基于重复片段的模式提出了新的重复片段定义LPR(largest pattern repetition)和模式单元的概念.对于长度为n的DNA序列,其中的LPR的数量是O(n)数量级的,但提供了与个数可多达n2/4的tandem repeat相同的重复片段信息.基于模式单元设计了可用于重复片段查找的全新索引--后继数组.后继数组有效地降低了索引空间,很好地突破了重复片段查找中的索引空间瓶颈.在后继数组上,通过模式单元可发现构成LPR的全部原子模式,并通过判断相同模式是否在原序列中连续出现完成LPR的查找.理论分析和实验结果均表明,设计的LPR查找算法的时间和空间复杂度均为O(n).
DNA序列中的重複片段在人類基因研究中有著非常重要的生物意義,因此,查找給定DNA序列中的重複片段是生物序列分析領域中的一箇重要課題.基于重複片段的模式提齣瞭新的重複片段定義LPR(largest pattern repetition)和模式單元的概唸.對于長度為n的DNA序列,其中的LPR的數量是O(n)數量級的,但提供瞭與箇數可多達n2/4的tandem repeat相同的重複片段信息.基于模式單元設計瞭可用于重複片段查找的全新索引--後繼數組.後繼數組有效地降低瞭索引空間,很好地突破瞭重複片段查找中的索引空間瓶頸.在後繼數組上,通過模式單元可髮現構成LPR的全部原子模式,併通過判斷相同模式是否在原序列中連續齣現完成LPR的查找.理論分析和實驗結果均錶明,設計的LPR查找算法的時間和空間複雜度均為O(n).
DNA서렬중적중복편단재인류기인연구중유착비상중요적생물의의,인차,사조급정DNA서렬중적중복편단시생물서렬분석영역중적일개중요과제.기우중복편단적모식제출료신적중복편단정의LPR(largest pattern repetition)화모식단원적개념.대우장도위n적DNA서렬,기중적LPR적수량시O(n)수량급적,단제공료여개수가다체n2/4적tandem repeat상동적중복편단신식.기우모식단원설계료가용우중복편단사조적전신색인--후계수조.후계수조유효지강저료색인공간,흔호지돌파료중복편단사조중적색인공간병경.재후계수조상,통과모식단원가발현구성LPR적전부원자모식,병통과판단상동모식시부재원서렬중련속출현완성LPR적사조.이론분석화실험결과균표명,설계적LPR사조산법적시간화공간복잡도균위O(n).
