Algorithms for Extraction of Common Patterns from Data in Bioinformatics

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

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.