Composition Patterns in Nucleotide Sequences

PI: Gary BensonProposal Number: 0073081机构：Mt. Sinai School of medicine项目概述该项目是对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.