一、
下面的HIERARCHICALCLUSTERING算法需要输入一个n*n的距离矩阵d,并产生数据的n个不同的分划,以树的形式输出。
HIERARCHICALCLUSTERING(d,n)
形成n个类,每个类含有一个元素
构建图T,为每个类分配一个单独的顶点
while 存在多于一个类
找到最近的2个类C1和C2
将C1和C2合并成一个新的类C,C含有|C1|+|C2|个元素
计算C与其他各类的距离
在图T中增加一个顶点C,且与C1和C2相连
在d中删除与C1和C2相对应的行和列
在d中为新类C增加一行一列
return T
二、
将一个n*m的表达矩阵的n行看成为m维空间中n个点的集合,将其划分成k个子集,并假定类的个数k是已知的。
K均值聚类问题
给定n个数据点,找到k个凝聚点,满足平方误差失真最小。
输入:含有n个点的集合v和参数k
输出:含有k个点(凝聚点)的集合,满足d(x,y)对X所有可能的选择为最小。
我们假设将n个元素的集合分划成k个类的每个分划P都有与之相关联的聚类成本,记为cost(P),以此来衡量分划P的质量:分划的聚类成本越低,聚类的效果就越好。
给定一个分划P、一个该分划下的类C以及类C外一个元素i,Pi->c表示在分划P中将元素i移动到类C中得到的分划。△(i->C)=cost(P)-cost(Pi->c)>0时,移动改善了聚类成本
PROGRESSIVEGREEDYK-MEANS(k)
选择一个任意分划P,将元素分成k个类。
while 不断循环
bestchange<-0
for 每个类C
for 每个元素i不属于C
if将i移动到类C中会减少聚类成本
if △(i->C)>bestchange
bestchange<-△(i->C)
i*<-i
C*<-c
ifbestchange>0
通过将i*移动到类C*来改进分划
else
returnP
三、有瑕图
确定将一个图转换成团图时所需要增加或者删除的最小边数
输入:图G
输出:将图G转换成一个团图需要增加或删除的最小边数
距离图上顶点表示不同的基因,且基因i和基因j之间有一条边相连,当且仅当这2个基因之间的距离小于阈值θ,即di,j<θ,对于一个合适地选择θ,一个满足同质性和差异性原则的基因聚类将对应于一个距离图,且该图是一个团图。
将基因i和类C之间的距离定义为基因i和类C中所有基因之间的平均距离:d(i,C),给定一个θ,如果d(i,C)<θ,则称基因i邻近于类C,反之称为基因i远离于类C。
CAST(G,θ)
S<-距离图G中顶点的集合
P<-φ(φ表示空集)
while S≠φ
v<-距离图G中度最大的顶点
C<-{v}
while存在一个邻近的基因i不属于C,或一个远离的基因i属于C
找到一个最邻近的基因i不属于C,并将其加到类C中
找到一个最远离的基因i属于C,并将其从类C中删除
将类C增加到分划P中
S<-S\C
从距离图G中剔除类C中的顶点
returnP
分享到:
相关推荐
使用基因聚类(RExGC)检索实验 该文件描述了下载,处理和分析以下数据的工作流程: Blomstedt,P.,Dutta,R.,Seth,S.,Brazma,A.和Kaski,S.(2016)。 基于建模的实验检索:基因表达聚类的案例研究。 生物信息...
选取方差最大的20个基因作为特征,使用层次聚类对着286个病人进行聚类,查看聚到一起的病人的预后信息或雌激素受体的信息是否比较接近,即聚在一起的病人是否具有相似的表型(理解聚类在系统生物学中的应用)。
模糊聚类是一种使用模糊集理论以分析复杂数据集的流行无监督学习技术。其目标是基于不同的相似度或距离度量将给定数据集中相似的...这种技术已被用于识别生物系统中的主要通路,以及识别不同基因标记之间的模式和关系。
通过傅里叶变换对 DNA 序列或全基因组进行系统发育分析:将 DNA 序列或基因组映射为基于DNA 序列的核苷酸组成。 甚至在将 DNA 序列的傅立叶功率谱缩放到序列的最长长度之后,计算不同长度的 DNA 序列的欧几里德距离...
在上界未知的测量噪声和参数变化的情况下,算法通过滑模量及其微分的符号构成控制律,实现了系统的镇定。仿真结果表明算法在噪声环境下能保证系统的稳定性,对参数不确定具有较强的鲁棒性。算法结构简单,便于实现。
构建了可在不同操作系统平台之间通用的基因表达模式分析软件系统。该软件集成了多种基因表达模式分析算法,并通过模块化设计保持了算法的可扩展性。同时具有原始数据可视化和过滤、多种相似性度量选择、聚类方法选择...
对其所翻译的氨基酸序列经比对和系统发生分析后,将该61个基因进行了分类,结果表明:该61个玉米WRKY转录因子中共有I类13个、Ⅱ类32个、Ⅲ类16个.聚类分析结果与该三类WRKY转录因子的进化关系相一致.对玉米WRKY...
对TBC特征矩阵进行平移极差变换,利用指数切比雪夫距离法构建了模糊相似矩阵,采用模糊聚类中的传递闭包法构建进化树。该方法不需要多序列比对,计算简单。对两组基因组序列构建进化树,实验结果验证了该方法的有效...
自组织特征映射神经网络与层次聚类算法是两种较经典的分析基因表达数据的聚类算法,但由于基因表达数据的复杂性与不稳定性,这两种算法都存在着自身的优劣。因此,在比较两种算法差异性的基础上,创造性地提出了一种新...
treeCl是一个 python 包,用于通过系统发育相似性对基因家族进行聚类。 它需要一组比对,推断它们的系统发育树,并根据树间距离矩阵对它们进行聚类。 最后,它为每个集群计算一个单一的代表树。 你可以在阅读论文 ...
该软件包含了两两平均连锁聚类法、系统聚类法、自组织特征映射法和模糊聚类等聚类算法,其中模糊聚类算法是首次用于基因表达模式分析。该软件同时具有数据过滤、多种相似性度量选择、聚类方法选择和结果可视化等功能...
汤氏细胞是一种将个体混合基因型scRNAseq实验进行聚类的方法。 输入仅是possorted_genome_bam.bam,以及从输出的条形码 。 souporcell由6个步骤组成,其中前3个步骤使用外部工具,最后一个使用此处提供的代码。 ...
复杂网络社团结构检测广泛的应用于信息推荐系统、致癌基因识别、数据挖掘等领域。近年来,社区检测得到了快速的发展,这主要是由于 Newman 提出了模块度(modularity)的概念,从而使得网络社区划分优劣可以有一个明确...
穆斯卡里(Muscari)是一种新的基于多任务图的聚类算法,通过使用物种与物种之间的系统发育关系,共同从物种特定的全基因组共表达网络中跨物种识别基因共表达模块(或子网络)。共表达矩阵的基于图的性质。 穆斯卡里...
在正常条件下,在萨哈农业研究站的实验农场种植了10种埃及大麦基因型(2个商业品种和8个育种系),并在埃及Elsharkia省El-hosainia平原... 使用这些不同的标记系统对研究的基因型进行聚类分析,发现四个树状图的拓扑结
边界森林聚类是用MATLAB编写的泛基因组聚类管道。 边界森林聚类分3个主要步骤完成: 边界森林。 这会基于序列相似性生成许多边界树(有关边界森林的更多详细信息,请参见)。 可以将一个序列作为新的代表添加到树上...
针对微阵列基因表达数据聚类的高维复杂性,提出了一种基于密度的并行聚类算法,在APRAM模型的分布式存储系统中,通过欧几里德距离矩阵和密度函数两次时间复杂度为O(■)的计算,可使聚类过程的时间复杂度为O(■),以...
在多Agent系统(MAS)环境中,协商是一个复杂的动态交互过程。如何提高协商效率,成为了研究者关注的焦点。应用记忆演化理论的强化学习思想,提出一种Agent协商算法。它与基本强化学习相比,3阶段的记忆演化的强化...
利用系统聚类分析方法对随机选取的3种哺乳动物的60个主要组织相容性复合体(MHCⅠ类和Ⅱ类)基因的mRNA序列进行了同义密码子使用概率偏性研究。结果发现,不同物种的MHC基因群中类型相同的基因具有相近的同义密码子...