Rubanov Lev I, Seliverstov Alexandr V, Zverkov Oleg A, Lyubetsky Vassily A
Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences, Bolshoi Karetnyi per. 19, Building 1, Moscow, 127051, Russia.
BMC Bioinformatics. 2016 Sep 20;17:385. doi: 10.1186/s12859-016-1257-5.
Perfectly or highly conserved DNA elements were found in vertebrates, invertebrates, and plants by various methods. However, little is known about such elements in protists. The evolutionary distance between apicomplexans can be very high, in particular, due to the positive selection pressure on them. This complicates the identification of highly conserved elements in alveolates, which is overcome by the proposed algorithm.
A novel algorithm is developed to identify highly conserved DNA elements. It is based on the identification of dense subgraphs in a specially built multipartite graph (whose parts correspond to genomes). Specifically, the algorithm does not rely on genome alignments, nor pre-identified perfectly conserved elements; instead, it performs a fast search for pairs of words (in different genomes) of maximum length with the difference below the specified edit distance. Such pair defines an edge whose weight equals the maximum (or total) length of words assigned to its ends. The graph composed of these edges is then compacted by merging some of its edges and vertices. The dense subgraphs are identified by a cellular automaton-like algorithm; each subgraph defines a cluster composed of similar inextensible words from different genomes. Almost all clusters are considered as predicted highly conserved elements. The algorithm is applied to the nuclear genomes of the superphylum Alveolata, and the corresponding phylogenetic tree is built and discussed.
We proposed an algorithm for the identification of highly conserved elements. The multitude of identified elements was used to infer the phylogeny of Alveolata.
通过各种方法在脊椎动物、无脊椎动物和植物中发现了完全或高度保守的DNA元件。然而，关于原生生物中的此类元件却知之甚少。顶复门生物之间的进化距离可能非常大，特别是由于它们受到正选择压力。这使得在肺泡虫中鉴定高度保守元件变得复杂，而本文提出的算法克服了这一难题。
开发了一种用于鉴定高度保守DNA元件的新算法。它基于在专门构建的多部分图（其部分对应于基因组）中识别密集子图。具体而言，该算法不依赖于基因组比对，也不依赖于预先确定的完全保守元件；相反，它快速搜索不同基因组中长度最大且差异低于指定编辑距离的单词对。这样的单词对定义了一条边，其权重等于分配给其两端的单词的最大（或总）长度。然后通过合并其一些边和顶点来压缩由这些边组成的图。通过类似细胞自动机的算法识别密集子图；每个子图定义一个由来自不同基因组的相似不可扩展单词组成的簇。几乎所有簇都被视为预测的高度保守元件。该算法应用于肺泡虫超门的核基因组，并构建和讨论了相应的系统发育树。
我们提出了一种鉴定高度保守元件的算法。所鉴定的大量元件被用于推断肺泡虫的系统发育。
