Algorithms for Extraction of Common Patterns from Data in Bioinformatics

研究了从DNA序列、蛋白质结构、二维电泳图像和基因表达数据等生物数据中提取共同模式的算法。主要取得了以下成果：1.基于局部对齐的公共模式提取。Gibbs抽样算法是一种广泛应用于序列数据中的公共模式提取算法。我们开发了一个变种的吉布斯采样算法，它可以应用于数值序列。我们将所提出的算法应用于蛋白质结构中模体的检测。2.从正负序列中提取模式的复杂性。我们研究了从正负序列中推导位置特异性得分矩阵的理论问题。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.