Composition Patterns in Nucleotide Sequences

PI：加里本森提案编号：0073081机构：Mt. Sinai School of Medicine项目概要该项目是对DNA序列中一种新型离散模式--组成模式--所产生的计算问题的研究。组成是一个描述特定字符串中每个字母出现频率的矢量。设S是E上的一个字符串，则C（S）=（f1; f2; pHj_ j）是S的合成，因此2 _，fi是S中i个字符的分数。组成图案是串P = r1 r2_ 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.