Algorithms for Extraction of Common Patterns from Data in Bioinformatics

从生物信息学数据中提取常见模式的算法

• 批准号: 13680394
• 负责人: AKUTSU Tatsuya
• 金额: $ 1.66万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680394/
• 关键词: Bioinformatics; Pattern matching; Sequence motif; Algorithms; Kernel method; Position specific score matrix; Local alignment; サポートベクタマシン; ローカルアライメント; ホモロジー検索; 点集合; 合同性判定; 最大共通部分点集合; 近似マッチング; モチーフ抽出; 最大クリーク; 電気泳動; スポットマッチング; 構造アライメント; GI

We studied algorithms for extracting common patterns from biological data such as DNA sequences, protein structures, two-dimensional electrophoresis image and gene expression data. We mainly obtained the following results.1.Extraction of Common Patterns by Local Alignment. The Gibbs sampling algorithm is widely-used for extraction of common patterns from sequence data. We developed a variant of the Gibbs sampling algorithm, which can be applied to numerical sequences. We applied the developed algorithm to detection of motifs from protein structures.2.On the Complexity of Deriving Patterns from Positive and Negative Sequences. We studied theoretical aspects of deriving position specific score matrices (PSSM) from positive and negative sequences.3.Pattern Matching Algorithms for Electrophoresis Image Data and Protein Structures. We formulated a pattern matching problem for 2-dimensional electrophoresis image data as a geometric matching problems and proved that it is NP-hard. On the other hand, we developed practical algorithms for computing optimal matchings for electrophoresis image data analysis and protein structure alignment.4.Kernel Method for Protein Sequence Classification. We developed a new kernel function for protein sequences based on the well-known local alignment algorithm for protein sequences. The kernel was combined with the support vector machine and was tested using some benchmark data. The results show that the new kernel is better than existing kernels.5.Inference of Protein-Protein Interactions Using Linear Programming. We developed a new method for inference of probabilities of domain-domain interactions from experimental data by formulating the inference problem as a linear program. The method was applied to inference of protein-protein interactions and was compared with existing methods. The results show that the proposed method outperforms existing methods for numerical data.

我们研究了从DNA序列、蛋白质结构、双向电泳图和基因表达数据等生物数据中提取常见模式的算法。我们主要取得了以下结果：1.基于局部比对的常见模式提取方法。Gibbs采样算法被广泛用于从序列数据中提取常见模式。我们开发了Gibbs抽样算法的一个变体，该算法可以应用于数字序列。将该算法应用于蛋白质结构中基序的检测。2.正负序列模式提取的复杂性。研究了从正负序列中提取位置特定的分数矩阵(PSSM)的理论问题。3.基于蛋白质结构和蛋白质结构的模式匹配算法。将二维电泳图像数据的模式匹配问题转化为几何匹配问题，并证明了该问题是NP难的。另一方面，针对电泳图数据分析和蛋白质结构比对，提出了计算最优匹配的实用算法。4.蛋白质序列分类的核方法。在著名的蛋白质序列局部比对算法的基础上，提出了一种新的蛋白质序列核函数。将该核函数与支持向量机相结合，并用一些基准数据进行了测试。实验结果表明，新的核函数优于已有的核函数。5.基于线性规划的蛋白质-蛋白质相互作用推理。通过将推理问题描述为线性规划，我们发展了一种新的方法来从实验数据推断域-域相互作用的概率。将该方法应用于蛋白质-蛋白质相互作用的推断，并与现有方法进行了比较。结果表明，该方法优于已有的数值数据处理方法。

项目成果

T.Akutsu, K.Kanaya, A.Ohyama, A.Fujiyama: "Point matching under non-uniform distortions"Discrete Applied Mathematics. 127. 5-21 (2003)

T.Akutsu、K.Kanaya、A.Ohyama、A.Fujiyama：“非均匀扭曲下的点匹配”离散应用数学。

A local search algorithm for local multiple alignment : special case analysis and application to cancer classification

局部多重比对的局部搜索算法：特例分析及其在癌症分类中的应用

• 发表时间: 2001
• 期刊: Proc. 2001 Int.Conf. Parallel and Distributed Processing Techniques and Applications
• 作者: T.Akutsu;S.Ott;T.Akutsu
• 通讯作者: T.Akutsu

Inferring a union of halfspaces from examples

从示例中推断半空间的并集

• 发表时间: 2002
• 期刊: Lecture Notes in Computer Science 2387
• 作者: T.Akutsu;S.Ott
• 通讯作者: S.Ott

遺伝子発現情報解析のための数理モデルとアルゴリズム

基因表达信息分析的数学模型和算法

• 发表时间: 2003
• 作者: T.Akutsu;S.Ott;T.Akutsu;阿久津達也
• 通讯作者: 阿久津達也

T.Akutsu, H.Bannai, S.Miyano, S.Ott: "On the complexity of deriving position specific score matrices from examples"Lecture Notes in Computer Science. 2373. 168-177 (2002)

T.Akutsu、H.Bannai、S.Miyano、S.Ott：“论从示例中导出位置特定分数矩阵的复杂性”计算机科学讲义。