Удалить элемент из списка на основе следующего элемента в том же списке

Question

Удалить элемент из списка на основе следующего элемента в том же списке

Я только начал изучать Python, и здесь у меня есть отсортированный список последовательностей белков (всего 59 000 последовательностей), и некоторые из них перекрываются. Я сделал список игрушек здесь, например:

ABCDE
ABCDEFG
ABCDEFGH
ABCDEFGHIJKLMNO
CEST
DBTSFDE
DBTSFDEO
EOEUDNBNUW
EOEUDNBNUWD
EAEUDNBNUW
FEOEUDNBNUW
FG
FGH

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

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
FEOEUDNBNUWD
FGH

Как мне это сделать? Мой код выглядит так:

with open('toy.txt' ,'r') as f:
    pattern = f.read().splitlines()
    print pattern

    for i in range(0, len(pattern)):
        if pattern[i] in pattern[i+1]:
            pattern.remove(pattern[i])
        print pattern

И я получил сообщение об ошибке:

['ABCDE', 'ABCDEFG', 'ABCDEFGH', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDE', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGH', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDE', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDE', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDE', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FG', 'FGH']
['ABCDEFG', 'ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']
Traceback (most recent call last):
  File "test.py", line 8, in <module>
    if pattern[i] in pattern[i+1]:
IndexError: list index out of range

21

python list bioinformatics

Источник

user10076625 13 июл '18 в 14:47

11 ответов

Другие вопросы по тегам python list bioinformatics

user7692463 13 июл '18 в 15:10 2018-07-13 15:10 · Answer 1 · 2018-07-13 15:10

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

Ошибка произошла из-за того, что вы изменяли один и тот же список при проверке индекса с помощью range() ,

Таким образом, при увеличении i Переменная вы удаляете элемент из списка, который в какой-то момент вызывает index error неизбежно.

Таким образом, вот рабочая версия вашего исходного кода с некоторыми изменениями,

pattern = ["ABCDE","ABCDEFG","ABCDEFGH","ABCDEFGHIJKLMNO","CEST","DBTSFDE","DBTSFDEO","EOEUDNBNUW","EAEUDNBNUW","FG","FGH"]
output_pattern = []


for i in range(0, (len(pattern)-1)):
    if not pattern[i] in pattern[i+1]:
        output_pattern.append(pattern[i]) 

# Adding the last item
output_pattern.append(pattern[-1])   
print (output_pattern)

>>>> ['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']

Обратите внимание, что этот код будет работать, если ваш список предварительно отсортирован, как вы упоминали в разделе комментариев.

Что делает этот код?

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

Что мне делать с последним предметом?

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

output_pattern.append(pattern[-1])

который добавляет последний элемент исходного списка.

Важная заметка

Этот ответ был написан в ответ на первоначальный вопрос ОП, где он хотел сохранить более продолжительное совпадение, и я цитирую, основываясь на следующем пункте в том же списке. Как заявляет @Chris_Rands, если ваши проблемы связаны с биологической задачей и вам необходимо найти какое-либо совпадение, это решение не подходит для ваших нужд.

Пример, где этот код не сможет распознать потенциальное перекрытие,

pattern = ["ACD", "AD", "BACD"]

где он будет выводить тот же результат, не удаляя возможные "ACD" перекрытия. Теперь, как пояснение, это подразумевало бы гораздо более сложный алгоритм, и я сначала подумал, что он выходит за рамки требований вопроса. Если когда-нибудь это ваш случай, я могу ошибаться, но я действительно считаю, что реализация C++ кажется более подходящей. взгляните на алгоритм CD-Hit, предложенный @Chris_Rands в разделе комментариев.

user4985733 13 июл '18 в 15:00 2018-07-13 15:00 · Answer 2 · 2018-07-13 15:00

Вы могли бы использовать groupby() а также max() чтобы помочь здесь:

from itertools import groupby

with open('toy.txt') as f_input:
    for key, group in groupby(f_input, lambda x: x[:2]):
        print(max(group, key=lambda x: len(x)).strip())

Это будет отображать:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EOEUDNBNUW
EAEUDNBNUW
FGH

groupby() работает, возвращая список совпадающих элементов на основе функции, в данном случае последовательных строк с одинаковыми первыми 2 символами. max() Затем функция берет этот список и возвращает элемент списка с самой длинной длиной.

user10035985 13 июл '18 в 15:01 2018-07-13 15:01 · Answer 3 · 2018-07-13 15:01

# assuming list is sorted:
pattern = ["ABCDE",
"ABCDEFG",
"ABCDEFGH",
"ABCDEFGHIJKLMNO",
"CEST",
"DBTSFDE",
"DBTSFDEO",
"EOEUDNBNUW",
"EAEUDNBNUW",
"FG",
"FGH"]

pattern = list(reversed(pattern))

def iterate_patterns():
    while pattern:
        i = pattern.pop()
        throw_it_away = False
        for p in pattern:
            if p.startswith(i):
                throw_it_away = True
                break
        if throw_it_away == False:
            yield i

print(list(iterate_patterns()))

Выход:

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']

user4531270 15 июл '18 в 00:49 2018-07-15 00:49 · Answer 4 · 2018-07-15 00:49

Код

import collections as ct


def read_file(filepath):
    """Yield a generator of lines from a file."""
    with open(filepath, "r") as f:
        for line in f:
            yield line.strip()


def find_longest_sequences(seqs):
    """Return a dict of the long common sequences."""
    seqs = tuple(seqs) 
    dd = ct.defaultdict(list)
    [dd[k].append(seq) for seq in seqs for k in seqs if k in seq]
    return {max(v, key=len) for v in dd.values()}


data = read_file("test.txt")
find_longest_sequences(data)

Выход

{'ABCDEFGHIJKLMNO',
 'CEST',
 'DBTSFDEO',
 'EAEUDNBNUW',
 'EOEUDNBNUWD',
 'FEOEUDNBNUW'}

подробности

Мы используем read_file выдавать каждую строку файла.

find_longest_sequences создает defaultdict, который группирует похожие последовательности вместе. Итерирует данные с двумя циклами:

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

Набор значений состоит из результирующего dict, и самые длинные последовательности возвращаются.

Обратите внимание на некоторые расхождения с ожидаемым результатом:

FGH пересекается с ABCDEFGHIJKLMNO и, таким образом, не является действительным выводом.
FEOEUDNBNUWD не оригинальная последовательность Постобработка необходима для перекрывающихся последовательностей.

user7326738 13 июл '18 в 15:01 2018-07-13 15:01 · Answer 5 · 2018-07-13 15:01

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

class Tree:
  def __init__(self, val=None):
    self.left, self.value, self.right = None, val, None
  def insert_val(self, _val):
    if self.value is None or _val.startswith(self.value):
       self.value = _val
    else:
       if _val < self.value:
          getattr(self.left, 'insert_val', lambda x:setattr(self, 'left', Tree(x)))(_val)
       else:
          getattr(self.right, 'insert_val', lambda x:setattr(self, 'right', Tree(x)))(_val)
  def flatten(self):
     return [*getattr(self.left, 'flatten', lambda :[])(), self.value, *getattr(self.right, 'flatten', lambda :[])()]

t = Tree()
for i in open('filename.txt'):
  t.insert_val(i.strip('\n'))
print(t.flatten())

Выход:

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']

user3545273 13 июл '18 в 15:24 2018-07-13 15:24 · Answer 6 · 2018-07-13 15:24

Простой способ - обработать входной файл по одной строке за раз, сравнить каждую строку с предыдущей и сохранить предыдущую, если она не содержится в текущей.

Код может быть таким простым, как:

with open('toy.txt' ,'r') as f:
    old = next(f).strip()               # keep first line after stripping EOL 

    for pattern in f:
        pattern = pattern.strip()       # strip end of line...
        if old not in pattern:
            print old                   # keep old if it is not contained in current line
        old = pattern                   # and store current line for next iteration
    print old                           # do not forget last line

user7003620 13 июл '18 в 15:00 2018-07-13 15:00 · Answer 7 · 2018-07-13 15:00

with open('demo.txt') as f:
    lines = f.readlines()

l_lines = len(lines)

n_lst = []

for i, line in enumerate(lines):
    line = line.strip()
    if i == l_lines - 1:
        if lines[-2] not in line:
            n_lst.append(line)
        break
    if line not in lines[i + 1]:
        n_lst.append(line)

print(n_lst)

Выход

['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EOEUDNBNUW', 'EAEUDNBNUW', 'FGH']

1

Источник

user7003620 13 июл '18 в 15:00

user5811078 13 июл '18 в 15:16 2018-07-13 15:16 · Answer 8 · 2018-07-13 15:16

Это приведет вас туда, где вы хотите быть:

with open('toy.txt' ,'r') as f:
    lines = f.readlines()
    data = set(lines)
    print(sorted([i for i in lines if len([j for j in data if j.startswith(i)])==1]))

#['ABCDEFGHIJKLMNO', 'CEST', 'DBTSFDEO', 'EAEUDNBNUW', 'EOEUDNBNUW', 'FGH']

я добавил set только в случае нескольких вхождений одного и того же текста.

1

Источник

user5811078 13 июл '18 в 15:16

user459745 15 июл '18 в 18:21 2018-07-15 18:21 · Answer 9 · 2018-07-15 18:21

Кенни, ты почти понял, но есть две проблемы, на которые указал @scharette:

for Цикл и удаление элемента списка не должны идти вместе. Исправление заключается в использовании while цикл и явно увеличить индекс. while цикл менее эффективен, потому что он вызывает len() несколько раз вместо одного, но это то, что нужно, чтобы получить правильный результат.
IndexError, Это происходит только в самой последней строке. Мой способ справиться с этой проблемой - игнорировать ошибку.

После этого я изменил ваш код:

with open('toy.txt' ,'r') as f:
    pattern = f.read().splitlines()
    print pattern

    try:
        i = 0
        while i < len(pattern):
            if pattern[i] in pattern[i+1]:
                pattern.remove(pattern[i])
            print pattern
            i += 1
    except IndexError:
        pass

user1394353 13 июл '18 в 23:41 2018-07-13 23:41 · Answer 10 · 2018-07-13 23:41

Не совсем соответствует вашим ожиданиям, но, учитывая, что вы заявляете, что это отсортировано (и это не так, EOEUDNBNUWD EAEUDNBNUW) и что я не знаю почему ты скучаешь EOEUDNBNUWD Я не уверен, правильно ли изложены ваши ожидания или я неправильно понял ваш вопрос.

(ах, да, я вижу понятие перекрытия бросает гаечный ключ в sort а также startswith подход).

Возможно, для ОП было бы неплохо перефразировать этот конкретный аспект, я прочитал комментарий @DSM, не понимая его проблемы. Теперь я делаю.

li = sorted([i.strip() for i in """
ABCDE
ABCDEFG
ABCDEFGH
ABCDEFGHIJKLMNO
CEST
DBTSFDE
DBTSFDEO
EOEUDNBNUW
EOEUDNBNUWD
EAEUDNBNUW
FEOEUDNBNUW
FG
FGH""".splitlines() if i.strip()])

def get_iter(li):
    prev = ""
    for i in li:
        if not i.startswith(prev):
            yield(prev)
        prev = i
    yield prev

for v in get_iter(li):
    print(v)

выход:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
EOEUDNBNUWD
FEOEUDNBNUW
FGH

user8451814 13 июл '18 в 17:34 2018-07-13 17:34 · Answer 11 · 2018-07-13 17:34

Как указывалось в других ответах, ваша ошибка возникает из-за того, что вы вычисляете длину ввода в начале, а затем не обновляете ее по мере сокращения списка.

Вот еще один вариант рабочего решения:

with open('toy.txt', 'r') as infile:
    input_lines = reversed(map(lambda s: s.strip(), infile.readlines()))

output = []
for pattern in input_lines:
    if len(output) == 0 or not output[-1].startswith(pattern):        
        output.append(pattern)

print('\n'.join(reversed(output)))