Efficient computation of absent words in genomic sequences
Efficient computation of absent words in genomic sequences
复制标题
DOI：
10.1186/1471-2105-9-167
复制
发表时间：
2008-03-26
影响因子：
3
通讯作者：
Giegerich, Robert
中科院分区：
文献类型：
--
作者：
Herold, Julia;Kurtz, Stefan;Giegerich, Robert
背景：序列组成分析是基因组研究中的一项常规任务。生物体的特征在于它们的碱基组成、二核苷酸相对丰度、密码子使用等。独特的序列是基因组比较、表达谱分析和基因工程中特别感兴趣的标记。相对于相同长度的随机序列，在真实的基因组中，独特的重复性被过度呈现。在最近的两项研究中，我们描述了一种新的算法和软件，用于计算缺失的单词。它比以前的算法更有效，更容易使用。它直接计算unword，而不需要指定长度估计。此外，它避免了后缀树和后缀数组等索引结构的空间需求。我们的实现是作为一个开源软件包提供的。我们计算人类和小鼠以及其他一些生物体的unwords，覆盖基因组大小范围从10（9）到10（5）bp。结论：新算法在标准硬件上仅使用2.5 Mb的空间，在10分钟内计算出人类基因组的缺失词。这使我们不仅能够对迄今为止最大的基因组进行这种类型的分析，而且还可以对新兴的泛基因组和元基因组数据进行分析。
Background: Analysis of sequence composition is a routine task in genome research. Organisms are characterized by their base composition, dinucleotide relative abundance, codon usage, and so on. Unique subsequences are markers of special interest in genome comparison, expression profiling, and genetic engineering. Relative to a random sequence of the same length, unique subsequences are overrepresented in real genomes. Shortest words absent from a genome have been addressed in two recent studies.Results: We describe a new algorithm and software for the computation of absent words. It is more efficient than previous algorithms and easier to use. It directly computes unwords without the need to specify a length estimate. Moreover, it avoids the space requirements of index structures such as suffix trees and suffix arrays. Our implementation is available as an open source package. We compute unwords of human and mouse as well as some other organisms, covering a genome size range from 10(9) down to 10(5) bp.Conclusion: The new algorithm computes absent words for the human genome in 10 minutes on standard hardware, using only 2.5 Mb of space. This enables us to perform this type of analysis not only for the largest genomes available so far, but also for the emerging pan- and meta-genome data.