The fast development of next-generation sequencing technology presents a major computational challenge for data processing and analysis.A fast algorithm,de Bruijn graph has been successfully used for genome DNA de nov...The fast development of next-generation sequencing technology presents a major computational challenge for data processing and analysis.A fast algorithm,de Bruijn graph has been successfully used for genome DNA de novo assembly;nevertheless,its performance for transcriptome assembly is unclear.In this study,we used both simulated and real RNA-Seq data,from either artificial RNA templates or human transcripts,to evaluate five de novo assemblers,ABySS,Mira,Trinity,Velvet and Oases.Of these assemblers,ABySS,Trinity,Velvet and Oases are all based on de Bruijn graph,and Mira uses an overlap graph algorithm.Various numbers of RNA short reads were selected from the External RNA Control Consortium(ERCC) data and human chromosome 22.A number of statistics were then calculated for the resulting contigs from each assembler.Each experiment was repeated multiple times to obtain the mean statistics and standard error estimate.Trinity had relative good performance for both ERCC and human data,but it may not consistently generate full length transcripts.ABySS was the fastest method but its assembly quality was low.Mira gave a good rate for mapping its contigs onto human chromosome 22,but its computational speed is not satisfactory.Our results suggest that transcript assembly remains a challenge problem for bioinformatics society.Therefore,a novel assembler is in need for assembling transcriptome data generated by next generation sequencing technique.展开更多
de Bruijn定理是一种重要的组合计数方法,本文以非常自然的方式推广了这种方法.P-图是图G在其顶点上的置换群P作用下形成的轨道.文中引进了P-图,P-图的色容指标,P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念,建立了色权...de Bruijn定理是一种重要的组合计数方法,本文以非常自然的方式推广了这种方法.P-图是图G在其顶点上的置换群P作用下形成的轨道.文中引进了P-图,P-图的色容指标,P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念,建立了色权多项式的计算公式和一系列的组合公式及性质.展开更多
Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining av...Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.展开更多
基金supported by grants from the National Center for Research Resources (5P20RR016471-12)the National Institute of General Medical Sciences (8 P20 GM103442-12) from the National Institutes of Healththe seed collaborative research grant from the Odegard School of Aerospace Sciences and the School of Medicine and Health Sciences at University of North Dakota
文摘The fast development of next-generation sequencing technology presents a major computational challenge for data processing and analysis.A fast algorithm,de Bruijn graph has been successfully used for genome DNA de novo assembly;nevertheless,its performance for transcriptome assembly is unclear.In this study,we used both simulated and real RNA-Seq data,from either artificial RNA templates or human transcripts,to evaluate five de novo assemblers,ABySS,Mira,Trinity,Velvet and Oases.Of these assemblers,ABySS,Trinity,Velvet and Oases are all based on de Bruijn graph,and Mira uses an overlap graph algorithm.Various numbers of RNA short reads were selected from the External RNA Control Consortium(ERCC) data and human chromosome 22.A number of statistics were then calculated for the resulting contigs from each assembler.Each experiment was repeated multiple times to obtain the mean statistics and standard error estimate.Trinity had relative good performance for both ERCC and human data,but it may not consistently generate full length transcripts.ABySS was the fastest method but its assembly quality was low.Mira gave a good rate for mapping its contigs onto human chromosome 22,but its computational speed is not satisfactory.Our results suggest that transcript assembly remains a challenge problem for bioinformatics society.Therefore,a novel assembler is in need for assembling transcriptome data generated by next generation sequencing technique.
文摘Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.
