Composition Patterns in Nucleotide Sequences

派：加里·本森提议电话：0073081机构：Mt.西奈医学院项目摘要这个项目是对DNA序列中一种新的离散模式--组合模式--所产生的计算问题的调查。组合模式是描述每个字母在特定字符串中出现的频率的矢量量。设S是E上的串，则C(S)=(f1；f2；pH j_j)是S的构图，因此2_，fi是S字中I的分数。构图模式是串P=r1r2__Rp，其中RI表示构图区域，即不同于其周围区域的同质构图的子串。请注意，RI中的字母顺序无关紧要，因为它对RI的组成没有影响。到目前为止，描述DNA功能位点的算法主要集中在识别本提案所称的位置特定模式，如共识序列或更灵活但不太特定的基于权重矩阵的模式图谱。不幸的是，特定于位置的模式通常没有足够的选择性来区分特征的实际出现和假阳性。通常，当使用这些模式来搜索未知匹配时，获得的假阳性比真阳性多一到几个数量级。合成模式是一种新的方法，它包含了一个重要的物理属性，即DNA双螺旋的结构构象(形状)可能发生变化，但它是在一种显然以前没有被算法社区探索过的离散模式的背景下进行的。DNA结晶研究支持这样一种观点，即某些二核苷酸基序赋予特定类型的灵活性。进一步的证据来自对固有的弯曲和可扭结的DNA的研究。基于这些观察，这里提出，对于构象灵活性，序列中核苷酸的顺序可能没有某些核苷酸或二核苷酸碱基偏差对整个序列的影响那么重要。支持这一论断的是越来越多的重要DNA特征的证据，这些特征的统一特征是成分偏见，而不是特定于位置的信息。这项研究项目包括针对三个相关问题领域的算法开发，这三个问题领域形成了理解核苷酸序列中组成变异的功能重要性和检测组成模式的基础。这些领域是：模式匹配。给出了构图模式和构图顺序。查找序列中该阵列的所有匹配项。出现次数可以是精确的，也可以是近似的。图案检测。给出了一个或一组序列。找出所有重复出现的作文模式。事件可以是精确的，也可以是近似的。模式未指定或仅部分指定序列分段。文中给出了一个序列。将其划分为统计上不同的同质成分区域。这些问题本身就有理论意义，与生物学无关，几乎没有受到算法界的关注。

PI: Gary BensonProposal Number: 0073081Institution: Mt. Sinai School of MedicineProject SummaryThis project is an investigation of computational problems that arise for a new type of discrete pattern in DNA sequences, the composition pattern.Composition is a vector quantity describing the frequency of occurrence of each alphabet letter in a particular string. Let S be a string over E.Then, C (S) =(f1; f2; pH j _ j) is the composition of S, wherefore 2 _, fi is the fraction of the characters in S that are i. A composition pattern is a string P = r1r2 _ _ _ rp, where RI represents a composition region i.e. a substring of homogenous composition which differs from that of its surrounding regions. Note that the order of letters in RI is irrelevant, as it has no effect on the composition of RI. To date, algorithms which characterize DNA functional sites have concentrated primarily on identifying what this proposal terms position-specific patterns, such as the consensus sequence or themore flexible, but less specific weight matrix based pattern profile. Unfortunately, position-specific patterns are usually not selective enough to distinguish actual occurrences of a feature from false positives. Too often, when these patterns are used to search for unknown matches, one to several orders of magnitude more false positives than true positives are obtained. The composition pattern is a new approach which embraces an important physical property, the potential for variation in structural conformation (shape) of the DNA double helix, yet does so in the context of a type of discrete pattern which has apparently not been previously explored by the algorithmic community. DNA crystallization studies support the idea that certain dinucleotides base-steps confer specific types of flexibility. Further evidence is provided by studies of intrinsically curved and `kinkable' DNA. Based on these observations, it is suggested here that for conformational flexibility, the order of nucleotides in a sequence may be less important than the effect, which certain nucleotide or dinucleotide base-step biases impart on the sequence as a whole. In support of this assertion is an accumulating body of evidence of important DNA features whose unifying characteristic is composition bias rather than position-specific information. This research project encompasses algorithm development for three related problem areas which form the basis for understanding the functional importance of composition variation in nucleotide sequences and the detection of composition patterns. These areas are:Pattern matching. A composition pattern and sequence are given. Find all occurrences of the pattern in the sequence. Occurrences may be exact or approximate.Pattern detection. A sequence or set of sequences is given. Find all recurring composition patterns. Occurrences may be exact or approximate. The patterns are not specified or only partially specifiedSequence segmentation. A sequence is given. Partition it into statistically distinct regions of homogenous composition. These problems have theoretical interest in their own right, independent of biology and have received almost no attention from the algorithmic community.