python - 包含多值条目的二等分列表？关于完成此任务的建议

Question

我真的需要一些关于使用什么数据结构和函数来解决我正在尝试执行的任务的建议。我只是不确定这里的最佳方法。

问题/任务:我有一个染色体开始和结束位置的列表。我正在尝试找出将这些数据插入元组列表(？)或类似内容的最佳方法，然后在给定 start_end 范围值的情况下将这些坐标一分为二。我之前使用过 bisect，但仅适用于包含单个值条目的列表所以只是不确定进行多值比较的最佳方法是什么。

例如，如果我有下面的基因，

gene_name start_pos end_pos
gene_A 100 200
gene_B 300 400
gene_C 500 600
gene_D 700 800
gene_E 900 1000

并且我想用一个开始和结束位置与正常开始和结束不匹配来查询这个列表，以返回匹配的基因；

query_start = 550 query_end = 580 > should return gene_C 
query_start = 110 query end = 180 > should return gene_A

我已经尝试过自己的方法并编写了一些丑陋得可笑的复杂代码，但我知道必须有一种简单/合乎逻辑的方法来做到这一点并且我正在努力提出正确的问题文档/论坛搜索明智。

如有任何有用的建议，我们将不胜感激。

谢谢

Answer 1

首先，这里是元组列表中的所有数据:

>>> txt='''\
... gene_name start_pos end_pos
... gene_A 100 200
... gene_B 300 400
... gene_C 500 600
... gene_D 700 800
... gene_E 900 1000'''
>>> 
>>> genes=[(name, int(d1), int(d2)) for name, d1, d2 in [line.split() for line in txt.splitlines()[1:]]]
>>> genes
[('gene_A', 100, 200), ('gene_B', 300, 400), ('gene_C', 500, 600), ('gene_D', 700, 800), ('gene_E', 900, 1000)]

一旦你有了它，对于你的简单示例，你可以使用过滤器:

def query(genes, start, finish):
    return list(filter(lambda t: t[1]<start<t[2] and t[1]<finish<t[2], genes))

>>> query(genes, 550, 580)
[('gene_C', 500, 600)]
>>> query(genes, 110, 180)
[('gene_A', 100, 200)]

或者列表理解:

def query(genes, start, finish):
    return [t[0] for t in genes if t[1]<start<t[2] and t[1]<finish<t[2]]

>>> query(genes, 550, 580)
['gene_C']
>>> query(genes, 110, 180)
['gene_A']

或者您可以使用 bisect module (如果基因是一个排序列表)。

首先对列表进行排序:

>>> genes.sort(key=lambda t: (t[1], t[2]))
>>> genes
[('gene_A', 100, 200), ('gene_B', 300, 400), ('gene_C', 500, 600), ('gene_D', 700, 800), ('gene_E', 900, 1000)]

生成可用作索引的键元组列表:

>>> keys=[(t[1], t[2]) for t in genes]
>>> keys
[(100, 200), (300, 400), (500, 600), (700, 800), (900, 1000)]

现在您可以使用键索引和二等分查询基因:

>>> import bisect
>>> genes[bisect.bisect_left(keys, (550, 580))-1]
('gene_C', 500, 600)
>>> genes[bisect.bisect_left(keys, (110, 180))-1]
('gene_A', 100, 200)

对于更复杂的示例，您可以考虑 SortedCollection食谱。