- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在努力解决这个生物信息学问题:https://stepic.org/lesson/An-Explosion-of-Hidden-Messages-4/step/1?course=Bioinformatics-Algorithms-2&unit=8
具体问题在上面链接的第5个窗口,问题是:大肠杆菌基因组中有多少不同的9-mers form (500,3)-clumps? (换句话说,不要多次计算一个 9 聚体。)
我的代码如下。这是错误的,我很想解释为什么,以及如何改进它(显然 O 效率很糟糕,但我几天前开始编写 Python...)非常感谢!
genome = '' #insert e. Coli genome here
k = 4 #length of k-mer
L = 50 #size of sliding window
t = 3 #k-mer appears t times
counter = 0
Count = []
for i in range(0,len(genome)-L): #slide window down the genome
pattern = genome[i:i+k] #given this k-mer
for j in range(i,i+L): #calculate k-mer frequency in window of len(L)
if genome[j:j+k] == pattern:
counter = counter + 1
Count.append(counter)
counter = 0 #IMPORTANT: reset counter after each i
Clump = []
for i in range(0,len(Count)):
if Count[i] == t: #figure out the window that has k-mers of frequency t
Clump.append(i)
Output = []
for i in range(0,len(Clump)):
Output.append(genome[Clump[i]:Clump[i]+k])
print " ".join(list(set(Output))) #remove duplicates if a particular k-mer is found more than once
print len(Output)
print len(list(set(Output))) #total number of Clump(k,L,t)
最佳答案
有趣的问题。 I've put up an implementation with a few tests on github here .请继续阅读以获取一些解释。
ben@nixbox:~/bin$ time python kmers.py ../E-coli.txt 9 500 3
(500, 3)-clumps of 9-mers found in that file: 1904
real 0m15.510s
user 0m14.241s
sys 0m0.956s
这里的这个问题(在大数据中很常见)实际上归结为选择正确的数据结构,并进行一些时间/空间权衡。如果你选择正确,你可以在时间上与你的基因组长度成线性关系,在空间上与你的滑动窗口长度成线性关系。但我已经超前了。让我们直观地解释一下这个问题(主要是为了我能够理解它:-))。
在此窗口中有一个 (20,3)- 3 聚体团:“CAT”。还有一些其他的(其中一个是“AAA”),但这个例子说明了 k、L 和 t 正在做什么。
现在,我们来谈谈算法。让我们进一步简化问题,以便我们可以想象我们将如何解析和存储它:让我们看一个简单的 (5,3)-3 聚体团。
括号表示我们这里宽度为 5 的滑动窗口。我们可以在我们的窗口中看到我们的 3 聚体分解为 ATA
、TAA
和 AAA
。当我们将窗口向右滑动一个时,ATA
退出,我们获得第二个 AAA
。当我们再次向右滑动窗口时,现在 TAA
退出,我们获得了第三个 AAA
- 我们找到了 AAA
的 (5,3) block AAA
s.
显然,这是微不足道的,但对于弄清楚我们如何处理更大的团 block 很有用——重要的是,当我们移动窗口时,我们不会丢弃整个先前窗口的数据;我们只是丢弃第一个 k-mer 并将新的添加到窗口的末尾。下一个见解是我们可以使用哈希支持结构(在 python 中,dict
s)在我们的窗口内对 k-mers 进行计数。这消除了对我们的数据结构进行线性搜索以确定其中有多少特定 k-mer 的需要。
因此,这两个要求 - 记住插入顺序和哈希支持的数据结构 - 意味着我们应该创建一个自定义类来维护 list
- 或者更好,deque
- 窗口中的每个 kmer,以及一个 dict
- 或者更好,Counter
- 跟踪双端队列中每个 kmer 的频率。请注意 OrderedDict
接近于为你完成所有这些,但不完全是;如果它的计数大于 1,则弹出最老的 kmer 是错误的。
您真正应该用来简化代码的另一件事是适当的 sliding window iterator .
综合起来:
def get_clumps(genome, k, L, t):
kmers = KmerSequence(L-k, t)
for kmer in sliding_window(genome, k):
kmers.add(kmer)
return kmers.clumps
class KmerSequence(object):
__slots__ = ['order', 'counts', 'limit', 'clumps', 't']
def __init__(self, limit, threshold):
self.order = deque()
self.counts = Counter()
self.limit = limit
self.clumps = set()
self.t = threshold
def add(self, kmer):
if len(self.order) > self.limit:
self._remove_oldest()
self._add_one(kmer)
def _add_one(self,kmer):
self.order.append(kmer)
new_count = self.counts[kmer] + 1
self.counts[kmer] = new_count
if new_count == self.t:
self.clumps.add(kmer)
def _remove_oldest(self):
self.counts[self.order.popleft()] -= 1
用法:
with open(genomefile) as f:
genome = f.read()
k = 9
L = 500
t = 3
clumps = get_clumps(genome, k,L,t)
如顶部所述,完整的代码 - 包括一些辅助功能和当脚本直接作为 __main__
运行时的处理 - 在 github here 上.随意 fork 等。
关于python - 在滑动窗口中寻找 k-mers,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26621695/
这是在我的 MainActivity 中用作 BroadcastReceiver 的代码 mRegistrationBroadcastReceiver = new BroadcastRecei
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我想在大部分时间隐藏 UISearchBar,只在用户需要时调用它来显示。 我在 Interface Builder 中放置了一个 UISearchBar 并将其隐藏在 View 后面,当用户单击按钮
我有一个包含 CCMenuItemImage 的菜单(“myMenu”)。我希望此菜单能够检测手指滑动并相应地滑动。 我的问题是 CCMenuItemImage 似乎吸收了触摸事件。当用户触摸 CCM
我正在寻找一个简单的 jQuery 或 Javascript 解决方案,以使导航侧边栏在用户向下滚动页面时顺利跟随用户。像这里一样:http://ucon-acrobatics.com/shop/ 任
我有一个 ListView 控件来显示项目,我想提供一个滑动/滑动手势来选择一个项目。我用 GestureRecognizer类来识别交叉滑动手势,但我还想通过水平移动选择的项目来为这个手势设置动画。
我想将 String 行标记化为标记(存储到 String 表中),并且我只能使用 java.io.*它是为了实现一个计算器。 例如:第一行:1+2+3第二行:1+ 2*3(标记之间有空格) 进入表{
我有一个 ListView 控件来显示项目,我想提供一个滑动/滑动手势来选择一个项目。我用 GestureRecognizer类来识别交叉滑动手势,但我还想通过水平移动选择的项目来为这个手势设置动画。
我有一个导航栏,当单击菜单图标时,它将滑入“#secondary-nav”并隐藏“#primary-nav”。然而 jquery 似乎没有显示“#secondary-menu”。下面提供的是 HTMl
这个问题已经有答案了: how to make a sliding up panel like the Google Maps app? (2 个回答) 已关闭 7 年前。 我正在寻找类似的实现,如下
我有 ViewPager(Slide) 和 3 张图片。共有三个图像是通过 Internet 下载的。如果我将图片换到服务器上的另一台服务器上,链接保持不变,但应用程序中的图片没有改变,仍然是缓存中的
我在 gridview 中创建了两个按钮。 我想达到以下目的,但不知道应该用什么方法? 首先我触摸第一个按钮,将显示 toast 1 msg。通过将我的手指滑到第二个按钮而不抬起我的手指,将显示 to
所以我设置了一个小的 jquery 动画,用户将鼠标悬停在容器上一段时间,这会导致容器 split ,然后显示内部信息。 我不希望鼠标一进入容器就开始动画,所以我在动画上放了一个delay()。现在动
这个问题在这里已经有了答案: Simulate swipe with mouse in javascript (5 个答案) 关闭 7 年前。
我希望我的 Sprite 像在冰上一样滑动。因此,如果他在地面上,那么他可以正常行走,但当他接触冰时,他会滑动,直到有东西阻止他。有谁知道如何才能做到这一点?谢谢 最佳答案 像“Sprite Move
我的代码有几个问题:HTML: Bellevue
我正在尝试实现从 fragment1 过渡到 fragment2 的滑动动画。我正在使用 setCustomAnimations 方法。而且我知道我需要使用框架方法来替换 fragment 。 我的代
我不知道你们是否听说过 app chomp,但应用程序中有一个布局,如下图所示。我想知道他们是如何设置的,我将如何使用它来为我自己的应用程序制作类似的东西。有趣的是,当你滑动时,没有像水平 Scrol
我想检测用户何时在一个单元格占据整个屏幕宽度的 collectionView 中向左或向右滑动。是否可以不添加手势识别器。我试过添加手势识别器,但只有当我们将 collectionView 的 scr
我正在尝试开发一个应用程序来复制类似 tinder 的基于滑动的提要。该应用程序的想法与火种非常相似,也具有向右滑动和向左滑动匹配功能。 到目前为止我做了什么-我在 MongoDB 中创建了一个刷卡集
我是一名优秀的程序员,十分优秀!