A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches.
A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches.
复制标题
DOI：
10.1093/bioinformatics/btq229
复制
发表时间：
2010-06-15
期刊：
影响因子：
--
通讯作者：
Mushegian A
中科院分区：
文献类型：
--
作者：
Kristensen DM;Kannan L;Coleman MK;Wolf YI;Sorokin A;Koonin EV;Mushegian A
动机：确定多个基因组中的直向同源基因是比较基因组学的一项基本任务。构建基因组间对称最佳匹配（SymBets）并将其加入聚类是一种流行的直系同源物定义方法，体现在几个软件程序中。尽管它们被广泛使用，这些程序的计算复杂性还没有得到彻底的研究。结果如下：在这项工作中，我们表明，在标准的方法迭代通过所有三角形的SymbBets，内存规模至少与这些三角形的数量，O（g3）（其中g =基因组的数量），和建设时间尺度与迭代通过每个对，即O（g6）。我们提出了边搜索算法，迭代的边在SymbBet图，而不是三角形的SymbBets，因此有一个最坏情况下的复杂度只有O（g3log g）。几个优化减少了运行时间，甚至进一步在现实稀疏图。在来自噬菌体（POG）和柔膜菌（MOG）的基因组的两个真实世界的数据集中，EdgeSearch算法的实现比原始算法快大约一个数量级，并且随着基因组数量的增加而更好地扩展，最终结果中只有微小的差异，并且比流行的OrthoMCL程序快60倍，其中所识别的直向同源物组之间有90%的重叠。可用性和实现：C++源代码可在ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/下载联系方式：dmk@stowers.org补充信息：补充材料可在生物信息学在线获得。
Motivation: Identifying orthologous genes in multiple genomes is a fundamental task in comparative genomics. Construction of intergenomic symmetrical best matches (SymBets) and joining them into clusters is a popular method of ortholog definition, embodied in several software programs. Despite their wide use, the computational complexity of these programs has not been thoroughly examined. Results: In this work, we show that in the standard approach of iteration through all triangles of SymBets, the memory scales with at least the number of these triangles, O(g3) (where g = number of genomes), and construction time scales with the iteration through each pair, i.e. O(g6). We propose the EdgeSearch algorithm that iterates over edges in the SymBet graph rather than triangles of SymBets, and as a result has a worst-case complexity of only O(g3log g). Several optimizations reduce the run-time even further in realistically sparse graphs. In two real-world datasets of genomes from bacteriophages (POGs) and Mollicutes (MOGs), an implementation of the EdgeSearch algorithm runs about an order of magnitude faster than the original algorithm and scales much better with increasing number of genomes, with only minor differences in the final results, and up to 60 times faster than the popular OrthoMCL program with a 90% overlap between the identified groups of orthologs. Availability and implementation: C++ source code freely available for download at ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/ Contact: dmk@stowers.org Supplementary information: Supplementary materials are available at Bioinformatics online.
登录
查看更多内容
影响因子：
4.3
作者：
Altenhoff, Adrian M.;Dessimoz, Christophe
通讯作者：
Dessimoz, Christophe
DOI：
10.1142/9781860948732_0022
发表时间：
2007-01-01
期刊：
Computational systems bioinformatics. Computational Systems Bioinformatics Conference
影响因子：
--
作者：
Fu, Zheng;Jiang, Tao
通讯作者：
Jiang, Tao
DOI：
10.2307/2412448
发表时间：
1970-01-01
期刊：
SYSTEMATIC ZOOLOGY
影响因子：
--
作者：
FITCH, WM
通讯作者：
FITCH, WM
影响因子：
3.7
作者：
Chen F;Mackey AJ;Vermunt JK;Roos DS
通讯作者：
Roos DS
影响因子：
12.3
作者：
Kondrashov FA;Rogozin IB;Wolf YI;Koonin EV
通讯作者：
Koonin EV