объединение значений для большого количества перекрывающихся интервалов словарных ключей

Question

У меня есть словарь словарей, в котором есть такие предметы

all={
    1:{ ('a',123,145):20, ('a',155,170):12, ('b',234,345): 34},
    2:{ ('a',121,135):10, ('a',155,175):28, ('b',230,345): 16},
    3:{ ('a',130,140):20, ('a',150,170):10, ('b',234,345): 30}, 
    ...
    n: {...}
}

edit: названия словарей даны мной произвольно в соответствии с именами файлов, из которых читаются исходные данные, я могу использовать любое значение, которое я хочу назвать этими словарями. Я хотел бы получить сумму этих значений для каждого перекрывающегося региона. Вывод, показывающий, как должны быть перекрытия, выглядит так:

 { ('a',121,122):10, ('a',123,130):30, ('a',131,135):50, 
   ('a',136,140):40,('a',141,145):20, ...}

edit: каждый словарь имеет непересекающиеся интервалы, поэтому в данном словаре никогда не бывает ('a', 2,10) и ('a', 3,12), но интервалы между словарями совпадают как начало и конец позиции не совпадают (т. е. ключи не совпадают между словарями).

Мне не нужно использовать структуру данных словаря, и, поскольку я создал этот словарь в первую очередь, если это проще сделать со списками, наборами и т. Д. Я могу получить данные в одной из этих структур, я может работать с другим решением на основе другой структуры данных.

Спасибо за вашу помощь.

Answer 1

Хорошо, теперь я думаю, что понял: в основном у вас есть несколько перекрывающихся интервалов, представленных столбцами в определенной позиции с заданной толщиной. Вы бы нарисовали эти столбики друг под другом и увидели, насколько они толстые в любой заданной точке.

Я думаю, что проще / быстрее всего злоупотреблять тем фактом, что у вас есть целые позиции для этого:

all={
    1:{ ('a',123,145):20, ('a',155,170):12, ('b',234,345): 34},
    2:{ ('a',121,135):10, ('a',155,175):28, ('b',230,345): 16},
    3:{ ('a',130,140):20, ('a',150,170):10, ('b',234,345): 30}
}

from collections import defaultdict
summer = defaultdict(int)
mini, maxi = 0,0
for d in all.values():
    for (name, start, stop), value in d.iteritems(): 
        # im completely ignoring the `name` here, not sure if that's what you want
        # else just separate the data before doing this ...
        if mini == 0:
            mini = start
        mini, maxi = min(mini, start), max(maxi, stop)
        for i in range(start, stop+1):
            summer[i]+=value

# now we have the values at each point, very redundant but very fast so  far
print summer

# now we can find the intervals:
def get_intervals(points, start, stop):
    cstart = start
    for i in range(start, stop+1):
        if points[cstart] != points[i]: # did the value change ?
            yield cstart, i-1, points[cstart]
            cstart = i

    if cstart != i:
        yield cstart, i, points[cstart]


print list(get_intervals(summer, mini, maxi))

При использовании только элементов 'a' это дает:

[(121, 122, 10), (123, 129, 30), (130, 135, 50), (136, 140, 40), (141, 145, 20), (146, 149, 0), (150, 154, 10), (155, 170, 50), (171, 175, 28)]

Редактировать: меня просто поразило, как это сделать действительно просто:

from collections import defaultdict
from heapq import heappush, heappop

class Summer(object):
    def __init__(self):
        # its a priority queue, kind of like a sorted list
        self.hq = []

    def additem(self, start, stop, value):
        # at `start` add it as a positive value
        heappush(self.hq, (start, value))
        # at `stop` subtract that value again
        heappush(self.hq, (stop, -value))

    def intervals(self):
        hq = self.hq
        start, val = heappop(hq)
        while hq:
            point, value = heappop(hq)
            yield start, point, val
            # just maintain the current value and where the interval started
            val += value
            start = point
        assert val == 0

summers = defaultdict(Summer)
for d in all.values():
    for (name, start, stop), value in d.iteritems():
        summers[name].additem(start, stop, value)

for name,s in summers.iteritems():
    print name, list(s.intervals())

Answer 2

Хорошо, если это хромосомы, давайте начнем с их отдельного отображения:

{"Chr1": {(121,122):10, (123,130):30, ...},
"Chr2": {(230,233):16, ...},
...
}

Числа, которые вы складываете, я полагаю, представляют собой какие-то оценки - оценки экспрессии или любые другие.

Если диапазон позиций (эти 121, 130 чисел, определяющих интервалы) достаточно мал - до нескольких тысяч - тогда вы, вероятно, избавите себя от головной боли, сохранив суммированную оценку для каждогопозиции, и просто добавив счет за интервал к каждой позиции в этом интервале.

Если они похожи на отдельные базовые позиции, и есть миллионы возможных позиций, вам нужно придерживаться интервалов.Таким образом, для каждой вам нужно проверить соответствующую хромосому на интервалы, которые она перекрывает, затем удалить их и разбить их на столько меньших интервалов, сколько необходимо для хранения всех различных суммированных баллов.

Вотгрубая структура, но она не завершена:

for (start, end), score in intervals_to_add.items():
    overlapping = {}
    for (start1, end1), score1 in current_chromosome.items():
        if start1 <= start <= end1 or start1 <= end <= end1:
            overlapping[(start1, end1)] = score1
    for interval in overlapping:
        current_chromosome.pop(interval)
    # Process overlapping into smaller intervals, adding in the current interval
    current_chromosome.update(new_intervals)