一种新的序列集保守信号识别算法

模体发现是计算机科学中的一个较为重要且具有一定挑战的问题,主要用于定位DNA序列集中的保守信号。首先,分析了已有的基于图聚类的模体发现算法MCL-WMR,讨论了它存在的两个缺陷。其次,针对这两个缺陷提出了MCL-WMR的改进算法iMCL-WMR。实验结果表明,所提DNA模体发现算法的时间性能好于所比较的算法MCL-WMR和qPMS9,能够在1个小时以内处理数百条输入序列,而且能够应对某些输入序列不含模体实例的测试数据。     

基于子序列全连接和最大团的时间序列模体发现算法

针对时间序列模体发现算法计算复杂，并且无法发现多实例模体的问题，提出基于子序列全连接和最大团的时间序列模体发现（TSSJMC）算法。首先，使用快速时间序列子序列全连接算法求得所有子序列之间的距离，生成距离矩阵；然后，设置相似性阈值，将距离矩阵转化为邻接矩阵，构造子序列相似图；最后采用最大团搜索算法从相似图中搜索最大团，最大团的顶点对应的时间序列为包含最多实例的模体。在公开的时间序列数据集上进行实验，选用已有的能够发现多实例模体的Brute Force和Random Projection算法作为对比对象，分别从准确性、效率、可扩展性和鲁棒性对TSSJMC算法进行分析并获得了客观的评判结果。实验结果表明，与Random Projection算法相比，TSSJMC算法在效率、可扩展性和鲁棒性法方面均有明显优势；与Brute Force算法相比，TSSJMC算法发现的模体实例数量虽略低，但其效率和可扩展性都优于Brute Force算法。因此，TSSJMC是质量和效率相平衡的算法。     

基于纳米计算结构上的生物序列模体发现算法

模体发现对于预测基因特殊功能位点和鉴别药物作用目标等有重要的应用价值.本文介绍了一种纳米计算平台系统结构模型—CellMatrix以及在其上实现的DNA序列模体发现算法.CellMatrix是一种针对纳米计算平台提出的由同构晶格组成的可重构系统结构.这种结构既便于大规模工业生产,也很容易使得各种计算机软硬件系统在其上实现,同时这种结构又具备良好的可扩放性,是未来实现成熟纳米计算平台的一种选择.基于CellMatrix结构,本文首先在晶格结构上设计基本字符比较单元,而后在此基础上逐层构建更高层次的子序列测试单元和单条序列处理架构,从而实现了基于模式驱动的模体发现算法.最后用晶格开销数目和晶格延迟给出该算法的时空开销.     

基于染色质免疫共沉淀的高通量测序数据集的 顺式调控模体发现算法

针对新一代测序（NGS）的染色质免疫共沉淀的高通量测序（ChIP-Seq）数据集的模体发现问题,提出一种基于费舍尔（Fisher）精确检验的模体发现算法——FisherNet。首先运用费舍尔精确检验计算所有k长短序的P值并筛选出模体的种子;然后,构建初始模体的位置赋权矩阵;最后,用位置赋权矩阵扫描所有k长短序形成最终模体。通过小鼠胚胎干细胞（mESC）和红细胞、人类淋巴母细胞系的ChIP-Seq数据集以及ENCODE数据库的数据进行验证,结果表明所提算法精度和计算速度均高于其他常见的模体发现算法,并且能够发现超过80%的已知转录因子核心模体及其辅调控因子模体。该算法在保证高精度的同时可以应用到大规模测序数据集。     

一种关于蛋白质模体的自动识别算法

随着生物信息学的发展，模体识别已经成为一种能够从生物序列中提取有用生物信息的方法。文中介绍了有关模体的一些概念，讨论了模体识别算法(MEME)的基础，即EM(expectation maximization)算法，由于MEME算法是建立在EM算法的基础上的，所以又由此引出了MEME算法，并对MEME算法的一些基本问题比如时间复杂度、算法性能等进行了详细讨论，对算法的局限性和有待改进的地方作了说明。实践证明，MEME是一个较好的模体识别算法，它能够识别出蛋白质或者DNA序列中单个或多个模体，具有很大的灵活性。     

转录调控网络模块和模体识别算法研究进展

转录调控网络是生物体遗传信息传递的整体表示,是人们理解基因表达过程的重要内容。识别转录调控网络的模块和模体是分析网络拓扑结构和组织方式的重要方法,是揭示转录调控机制、生物发育与进化过程的重要环节之一。通过分析比较近年来用于转录调控网络模块识别的三类典型算法,阐述了它们各自的优势和不足。介绍了一种被广泛使用的转录调控网络模体识别算法。以此为基础,提出了转录调控网络模块和模体识别算法未来的研究方向。     

一种关于蛋白质模体的自动识别算法

随着生物信息学的发展,模体识别已经成为一种能够从生物序列中提取有用生物信息的方法.文中介绍了有关模体的一些概念,讨论了模体识别算法(MEME)的基础,即EM(expectation maximization)算法,由于MEME算法是建立在EM算法的基础上的,所以又由此引出了MEME算法,并对MEME算法的一些基本问题比如时间复杂度、算法性能等进行了详细讨论,对算法的局限性和有待改进的地方作了说明.实践证明,MEME是一个较好的模体识别算法,它能够识别出蛋白质或者DNA序列中单个或多个模体,具有很大的灵活性.     

(l,d)-模体识别问题的遗传优化算法

转录因子结合位点识别在基因表达调控过程中起着重要的作用.文中提出了一种贝叶斯模型驱动的模体识别的遗传优化算法GOBMD(Genetic Optimization with Bayesian Model for Motif Discovery).GOBMD首先使用一个基于位置加权散列的投影过程,将输入序列中的l-mers投影到k维(k相似文献   

基于时序模体注意力图卷积的动态网络链路预测算法

时序网络中的动态链路预测旨在基于历史连边信息预测未来会产生的连边,是网络分析的重要组成部分,具有极大的理论研究价值和广阔的应用场景.针对现有的动态链路预测算法大多基于一阶连边关系预测未来连边,忽略了对高阶的拓扑信息和时序通联信息的挖掘和利用问题,提出一种基于时序模体注意力图卷积的动态链路预测算法.首先,提出一种时序模体邻接矩阵构建算法,利用时序模体抽取节点间的高阶拓扑和时序关系信息;然后利用隐式调节过程对网络演化过程进行建模,并使用时序模体邻接矩阵作为传输矩阵的图卷积神经网络学习节点的低维向量表示并进行迭代更新;最后以节点间表示向量作为输入,通过计算连边发生的条件密度函数值作为依据完成动态链路预测.在多个真实时序网络数据集上的实验结果表明,所提算法可有效挖掘节点间的高阶拓扑和时序信息,提高动态链路预测效果.     

融合二连通模体结构信息的节点分类算法

节点表示学习将图结构数据信息编码到低维的潜在空间中,在节点分类、聚类、链路预测等机器学习任务中被广泛应用。在复杂网络中,节点与节点之间不仅存在直接相连的低阶结构,也存在以特殊连接模式形成的高阶结构,称为模体。提出一种融合二连通模体结构信息的节点分类算法(FMI),利用节点间高阶二连通模体信息学习节点表示,完成节点分类任务。首先,统计网络中的二连通模体,利用其中信息提出一个节点重要性的度量指标——模体比值。根据模体比值计算采样概率进行邻域采样;构造一个带权辅助图以融合网络节点连接的低阶关系与高阶关系,对节点进行加权邻域聚合以得到节点表示。在5个数据集Cora、Citeseer、Pubmed、Wiki和DBLP上执行节点分类任务,与5种经典基准算法进行对比,所提算法FMI在准确度和F1-分数等指标上表现良好。     

Particle Swarm Optimisation for Protein Motif Discovery

In this paper, a modified particle swarm optimisation algorithm is proposed for protein sequence motif discovery. Protein sequences are represented as a chain of symbols and a protein sequence motif is a short sequence that exists in most of the protein sequence families. Protein sequence symbols are converted into numbers using a one to one amino acid translation table. The simulation uses EGF protein and C2H2 Zinc Finger protein families obtained from the PROSITE database. Simulation results show that the modified particle swarm optimisation algorithm is effective in obtaining global optimum sequence patterns, achieving 96.9 and 99.5 classification accuracy respectively in EGF and C2H2 Zinc Finger protein families. A better true positive hit result is achieved when compared to the motifs published in PROSITE database.     

Exploring variable-length time series motifs in one hundred million length scale

The exploration of repeated patterns with different lengths, also called variable-length motifs, has received a great amount of attention in recent years. However, existing algorithms to detect variable-length motifs in large-scale time series are very time-consuming. In this paper, we introduce a time- and space-efficient approximate variable-length motif discovery algorithm, Distance-Propagation Sequitur (DP-Sequitur), for detecting variable-length motifs in large-scale time series data (e.g. over one hundred million in length). The discovered motifs can be ranked by different metrics such as frequency or similarity, and can benefit a wide variety of real-world applications. We demonstrate that our approach can discover motifs in time series with over one hundred million points in just minutes, which is significantly faster than the fastest existing algorithm to date. We demonstrate the superiority of our algorithm over the state-of-the-art using several real world time series datasets.     

基于不同算法的Motif预测比较分析与优化

研究转录因子结合位点（TFBs）的主要预测模型及其预测的算法,通过基于调控元件预测的3种代表性的算法MEME、Gibbs采样和Weeder预测拟南芥基因组。比较结果表明,Gibbs采样算法和Weeder算法预测长、短motif效率较高。重点分析MEME算法,提出结合不同算法查找motif的优化方法,并以实验验证该方法能有效提高预测效率。     

基于颜色和基元特征的图像检索

为了有效地提高图像检索性能,提出一种基于基元特征和颜色特征相结合的图像检索方法。检测彩色图像的边缘梯度,对其进行变换获得基元图像。以基元图像的重心为基准点计算各点到重心的距离,求得基元重心距离直方图。对基元图像中的每一个基元在4个不同方向投影,求得基元投影直方图。将彩色图像在RGB空间量化到64色颜色空间,得到彩色图像的颜色直方图。利用以上3个直方图描述图像特征,并用于图像检索。实验结果表明,该算法的查全率和查准率均有较大提高。     

基于小波和动态时间弯曲的主题查找算法 *

针对以前查找图形主题算法的精度和时间复杂度不能兼容的问题,提出了基于小波和动态时间弯曲 （DTW）的形状主题查询算法。本算法先利用小波变换进行数据降维并剪枝,以降低计算查找主题的复杂度;再 应用DTW的高精度计算的特点来查找图形主题,同时结合v-shift公式,忽略了在垂直方向的距离,这样查找图 形主题可以解决在现实世界中因形状大小不同而相似的问题。实验结果表明该方法具有较高的匹配精度和较 低的计算代价,可以找到图形相似的主题,并不会产生漏报,具有很强的实际意义。     

Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization

The MEME algorithm extends the expectation maximization (EM) algorithm for identifying motifs in unaligned biopolymer sequences. The aim of MEME is to discover new motifs in a set of biopolymer sequences where little or nothing is known in advance about any motifs that may be present. MEME innovations expand the range of problems which can be solved using EM and increase the chance of finding good solutions. First, subsequences which actually occur in the biopolymer sequences are used as starting points for the EM algorithm to increase the probability of finding globally optimal motifs. Second, the assumption that each sequence contains exactly one occurrence of the shared motif is removed. This allows multiple appearances of a motif to occur in any sequence and permits the algorithm to ignore sequences with no appearance of the shared motif, increasing its resistance to noisy data. Third, a method for probabilistically erasing shared motifs after they are found is incorporated so that several distinct motifs can be found in the same set of sequences, both when different motifs appear in different sequences and when a single sequence may contain multiple motifs. Experiments show that MEME can discover both the CRP and LexA binding sites from a set of sequences which contain one or both sites, and that MEME can discover both the –10 and –35 promoter regions in a set of E. coli sequences.     

Ranking and significance of variable-length similarity-based time series motifs

The detection of very similar patterns in a time series, commonly called motifs, has received continuous and increasing attention from diverse scientific communities. In particular, recent approaches for discovering similar motifs of different lengths have been proposed. In this work, we show that such variable-length similarity-based motifs cannot be directly compared, and hence ranked, by their normalized dissimilarities. Specifically, we find that length-normalized motif dissimilarities still have intrinsic dependencies on the motif length, and that lowest dissimilarities are particularly affected by this dependency. Moreover, we find that such dependencies are generally non-linear and change with the considered data set and dissimilarity measure. Based on these findings, we propose a solution to rank (previously obtained) motifs of different lengths and measure their significance. This solution relies on a compact but accurate model of the dissimilarity space, using a beta distribution with three parameters that depend on the motif length in a non-linear way. We believe the incomparability of variable-length dissimilarities could have an impact beyond the field of time series, and that similar modeling strategies as the one used here could be of help in a more broad context and in diverse application scenarios.     

基于Gibbs采样与遗传算法的模体识别

借鉴Gibbs采样思想,将序列峰值所对应的候选模体作为遗传算法的初始种群,提出一种改进的模体识别算法。将模体在序列中的出现次数作为变量加入到适应度函数中,使其更符合生物数据的特性。在算法变异操作中加入IUPAC简并码保持种群的多样性。对DBTSS数据库中的真实数据进行测试,结果表明该算法具有较高的识别精度和较快的搜索速度。