CuMen:基于最大频繁序列模式的聚类算法及其在基因拼接中的应用  

CuMen: Clustering Sequences Based on Maximal Frequent Sequential Pattern and its Application in Genome Sequence Assembly

作　　者：黄东[1] 唐俊[1] 汪卫[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机科学》2005年第10期149-153,共5页Computer Science

基　　金：本课题得到教委高校网格项目200309;上海科委重大项目03dz15027资助

摘　　要：基因组序列拼接的主流方法是将整条序列随机打断成小片段,然后根据片段间重叠关系连接成长序列。由于较多噪音存在,算法复杂度高,加之生物数据的海量增长,序列拼接处理导致巨大的时空开销而无法完成。本文提出一种基于最大频繁序列模式的聚类算法,将整个数据集分成若干个子集,分别高效地处理,实现了一个基因拼接网格系统、透明动态的资源管理,大大扩展了基因拼接计算能力。基于最大频繁序列模式聚类算法及挖掘算法,针对生物数据的特性做出了优化。Sequencing genomes is a fundamental aspect of biological research. A variety of assembly programs have been previously proposed and implemented. Because of great computational complexity and increasingly large size, they incur great time and space overhead. In realistic applications, sequencing process might come to become unacceptably slow for insufficient memory even with a mainframe with huge RAM. This paper offeres a clustering algorithm based on maximal frequent sequential patterns,aiming at divide the whole dataset into several parts which can be processed independently and efficiently in limited memory. Some techniques are applied to optimize the mining and clustering procedure. This approach is introduced into grid environment, exploiting parallelism and distribution for improving scalability further.

关 键 词：最大频繁序列模式 序列聚类 序列拼接 网格 基因组序列 序列模式 拼接处理 聚类算法 应用 生物数据 算法复杂度 网格系统 资源管理 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] Q987[自动化与计算机技术—计算机科学与技术]