在Hadoop和Java中实现算法

Question

你好，我正在尝试在Hadoop和Java中实现一个新的生物信息学算法（我不确定是否可行）。我已经在互联网上搜索了很多关于在Hadoop上实现算法的资料。然而，我发现的都是"识别并执行在Hadoop上的并行任务"。如果你们能够指导我在互联网上找到一些除了单词计数之外的使用Java在Hadoop上的实例，我将不胜感激。

这就是我想做的事情

我有一个非常大的文本文件（约100 MB），其中包含随机排列的字符（A、G、T、C）。长序列的随机排列的A、G、T、C可能形成一个重要的序列k，例如（ATCGAGC）。我可能会在这个名为'r'的文本文件的许多行中找到这个序列k-mer。

我需要执行以下任务

1. 在R（整个集合/文件）中识别所有文本（r）行中各种k-mer的位置。

2. 我必须跟踪特定r中k-mer的位置。

3. 我有两个参数用于比较不同r中的k-mer。

4. 如果两个'r'中的k-mer满足上述参数比较，我必须更新邻居集N。

如果你有兴趣，这是伪代码：

Given k, ĥ, ȇ
    1.  Make K  by extracting all possible kmers  from Reads
    2.  for all reads r belongs R do
            construct Gk[r] by scanning through r
            end for
    3.  for all k ε K do
                   for all read pairs (r,s) ε Gk × GK
                    if h(r,s) ≥ ĥ  and dk < ȇ h(r,s) then
                         update the N
                    end if
            end for
        end for

       k is k-mer
       K is set of all k
       ĥ minimum overlap distance
       ȇ maximum mismatch tolerance
       N neighbor set
       h(r,s)   overlap length of r and s wrt k
       d(r,s) distance between r and s

- user1772218

Answer 1

首先，这个问题看起来像是“集合相似性”问题。有很多这样的问题在MapReduce平台上有不同的效率。可以从这里开始查找http://infolab.stanford.edu/~ullman/mmds.html第三章。但前提是你的主要任务是学习Hadoop。如果不是的话...

其次，100MB对于Hadoop来说是非常小的数据量。绝对不需要使用Hadoop。即使只启动不超过2个并行任务（默认情况下，Hadoop每64MB启动1个任务），您也可以使用纯Java实现任何相似性算法，并且速度会更快。

- octo

---

是的，我同意Octo的观点。当我们处理大规模数据，数据量超过10GB时，应该使用Hadoop。 - Sandeep

谢谢大家。这正是我要找的东西。实际上，100 mob只是一个样本文件。真正的基因组文件可能会非常巨大。 - user1772218

此外，这只是算法的三个步骤之一。当在单个节点上应用时，该算法会生成160 GB的数据。这就是在Hadoop上实现的原因。对于我的幼稚问题表示歉意。我真的很感激这个解决方案。我认为这就是我一直在寻找的东西。 - user1772218

Answer 2

看起来是在输入文件中查找模式。请查看Grep.java和相关文件。它不能解决OP中的确切问题，但是是最接近的匹配。

- Praveen Sripati