겹치는 숫자 범위를 연속 범위로 병합

Question

게놈 좌표 범위를 연속 범위로 병합하려고합니다. 간격을 통해 병합하는 추가 옵션이 있습니다.

예를 들어, 게놈 범위가 [[0, 1000], [5, 1100]] 인 경우, 결과는 [0, 1100]이되고 싶습니다. 오프셋 옵션이 100으로 설정되고 입력이 [[0, 1000], [1090, 1000]] 인 경우 다시 한 번 결과가 [0, 1100]이 되길 원합니다.

정렬을 순차적으로 수행하고 이전 종료 위치와 다음 시작 위치를 병합하려고 시도했지만 실제 결과의 길이가 다양하기 때문에 실패합니다. 예를 들어, 내 목록에 [[138, 821],[177, 1158], [224, 905], [401, 1169]]이라는 결과가 시작 위치별로 정렬되어 있습니다. 그 대답은 [138, 1169]이어야하지만 대신 [[138, 1158], [177, 905], [224, 1169]]이 나옵니다. 분명히 이전 결말 및 다음 시작보다 더 많은 것을 고려해야하지만 좋은 해결책을 찾지 못했습니다 (if 문의 거대한 둥지가 아닌 것이 좋습니다). 누구든지 어떤 제안이 있습니까?

def overlap_alignments(align, gene, overlap): 
    #make sure alignments are sorted first by chromosome then by start pos on chrom 
    align = sorted(align, key = lambda x: (x[0], x[1])) 
    merged = list() 
    for i in xrange(1, len(align)): 
     prv, nxt = align[i-1], align[i] 
     if prv[0] == nxt[0] and prv[2] + overlap >= nxt[1]: 
      start, end = prv[1], nxt[2] 
      chrom = prv[0] 
      merged.append([chrom, start, end, gene]) 
    return merged 

Answer 1

글쎄, 모든 시작과 끝 및 각 위치가 속한 범위의 수를 추적하는 것은 어떻습니까?

def overlap_alignments(align, overlap): 
    # create a list of starts and ends 
    stends = [ (a[0], 1) for a in align ] 
    stends += [ (a[1] + overlap, -1) for a in align ] 
    stends.sort(key=lambda x: x[0]) 

    # now we should have a list of starts and ends ordered by position, 
    # e.g. if the ranges are 5..10, 8..15, and 12..13, we have 
    # (5,1), (8,1), (10,-1), (12,1), (13,-1), (15,-1) 

    # next, we form a cumulative sum of this 
    s = 0 
    cs = [] 
    for se in stends: 
     s += se[1] 
     cs.append((se[0], s)) 
    # this is, with the numbers above, (5,1), (8,2), (10,1), (12,2), (13,1), (15,0) 
    # so, 5..8 belongs to one range, 8..10 belongs to two overlapping range, 
    # 10..12 belongs to one range, etc 

    # now we'll find all contiguous ranges 
    # when we traverse through the list of depths (number of overlapping ranges), a new 
    # range starts when the earlier number of overlapping ranges has been 0 
    # a range ends when the new number of overlapping ranges is zero 
    prevdepth = 0 
    start = 0 
    combined = [] 
    for pos, depth in cs: 
     if prevdepth == 0: 
      start = pos 
     elif depth == 0 
      combined.append((start, pos-overlap)) 
     prevdepth = depth 

    return combined 

설명하는 것보다 그리기가 쉽습니다. (그리고 예, 누적 합계는 더 짧은 공간에 쓰여질 수 있지만이 방법이 더 명확합니다.)

그래픽으로 설명하려면 입력 ([5,10], [8,15], [ 12,13], [16,20]) 및 overlap = 1이다.

.....XXXXXo.............. (5-10) 
........XXXXXXXo......... (8-15) 
............Xo........... (12-13) 
................XXXXo.... (16-20) 
.....1112221221111111.... number of ranges at each position 
.....----------------.... number of ranges > 0 
.....---------------..... overlap corrected (5-20) 

Answer 2

파이썬은 batteries included 제공 :

from itertools import chain 

flatten = chain.from_iterable 

LEFT, RIGHT = 1, -1 

def join_ranges(data, offset=0): 
    data = sorted(flatten(((start, LEFT), (stop + offset, RIGHT)) 
      for start, stop in data)) 
    c = 0 
    for value, label in data: 
     if c == 0: 
      x = value 
     c += label 
     if c == 0: 
      yield x, value - offset 

if __name__ == '__main__': 
    print list(join_ranges([[138, 821], [900, 910], [905, 915]])) 
    print list(join_ranges([[138, 821], [900, 910], [905, 915]], 80)) 

결과 :

[(138, 821), (900, 915)] 
[(138, 915)] 

작동 원리 : 우리는 모든 시작과 같은 엔드 포인트, 우리가 정렬 이후 우리는 단순히 를 셀 라벨 모든 시작 지점에 대해까지 그리고 모든 종점에 대해까지 을 내린다. 같은 수의 시작점과 끝점을 방문하면 닫힌 (조인 된) 범위가 있습니다.