Биссектрисы, содержащие многозначные записи? Советы по подходу к этой задаче

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 (если genes - отсортированный список).

Сначала отсортируйте список:

>>> 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.

Answer 2

Поместить эти значения в словарь - это естественно. Здесь я использовал имена генов в качестве ключей словаря и соответствующие им диапазоны в качестве значений.

genes={'gene_A': [100,200],
    'gene_B': [300, 400],
    'gene_C': [500, 600],
    'gene_D': [700, 800],
    'gene_E': [900, 1000]}

#Takes as argument a dictionary of genes to check and a range in the form of a tuple
def gene_query(gene_data,gene_range):
    for gene in gene_data:
        if gene_range[0]>=gene_data[gene][0]:
            if gene_range[1]<=gene_data[gene][1]:
                return gene
    else:
        return "No genes match your query range"


print gene_query(genes, (550, 580))
print gene_query(genes, (110, 180))

Здесь я сделал функцию python, которая возвращает имя первого гена, совпадающего с диапазоном запроса, но вы можете легко изменить его так, чтобы он собирал все результаты, соответствующие запросу, добавляя соответствующие результаты в список, а не сразу возвращая их.