Remove item from list based on the next item in sa

问题:

I just started learning python and here I have a sorted list of protein sequences (total 59,000 sequences) and some of them overlap. I have made a toy list here for example:

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

I would like to remove those shorter overlap and just keep the longest one so the desired output would look like this:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
FEOEUDNBNUWD
FGH

How can I do it? My code looks like this:

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

And I got the error message:

['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

回答1:

There is other working answers, but none of them explain your actual problem. you were actually really close of a valid solution and what is, in my opinion, the most readable answer.

The error came from the fact that you were mutating the same list while checking for index using range().

Thus, while increasing the i variable you were removing item from the list which at one point causes the index error inevitably.

Therefore, here is a working version of your initial code with some changes,

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']    

Note that this code will work if your list is previously sorted as you mentioned in comment section.

What is this code doing ?

Basically, it use the same logic of your initial answer where it iterates on the list and check if the next item contains the current item. But, using another list and iterating until the before last item, will fix your index problem. But now comes a question,

What should I do with the last item ?

Since the list is sorted, you can consider the last item as always being unique. This is why I'm using

output_pattern.append(pattern[-1])

which adds the last item of the initial list.

Important note

This answer was written in response to OP's initial question where he wanted to keep the longer overlap and I quote based on the next item in same list. As stated by @Chris_Rands if your concerns are related to a biological task and need to find any overlap, this solution is not suited for your needs.

Example where this code would fail to recognize a potential overlap,

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

where it would output the same result without removing the possible "ACD" overlap. Now, just as a clarification though, this would imply a much more complex algorithm and I initially thought it was out of the scope of the question's requirements. If ever this is your case, I may be completely wrong here, but I truly think a C++ implementation seems more appropriate. have a look at the CD-Hit algorithm suggested by @Chris_Rands in the comment section.

回答2:

You could use groupby() and max() to help here:

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())

This would display:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EOEUDNBNUW
EAEUDNBNUW
FGH

groupby() works by returning a list of matching items based on a function, in this case consecutive lines with the same first 2 characters. The max() function then takes this list and returns the list item with the longest length.

回答3:

# 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()))

Output:

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

回答4:

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)

Output

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

回答5:

You can use a binary tree whose insertion process attempts to find nodes that precede the value:

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())

Output:

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

回答6:

This will get you where you want to be:

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']

I've added set just in case of multiple occurrences of same text.

回答7:

A simple way is to process the input file one line at a time, compare each line with the previous one and keep previous one if it is not contained in current one.

Code can be as simple as:

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

回答8:

Not an exact match with your expectations, but, given that you state it's sorted (and it's not, near EOEUDNBNUWD EAEUDNBNUW) and that I don't know why you're missing EOEUDNBNUWD I am not sure if your expectations are correctly stated or if I've misread your question.

(ah, yes, I see the notion of overlap throws a wrench into the sort and startswith approach).

Might be nice for the OP to restate that particular aspect, I read @DSM comment without really understanding his concern. Now I do.

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)

output:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
EOEUDNBNUWD
FEOEUDNBNUW
FGH

回答9:

Kenny, You almost got it, but there are two problems which @scharette pointed out:

1. for loop and removing of list item should not go together. The fix is to use the while loop and explicitly increase the index. The while loop is less efficient because it calls len() several times instead once, but that's what it take to get the correct result.
2. The IndexError. This only happens at the very last line. My way to deal with this problem is to ignore the error.

With that, I modified your code to:

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

回答10:

Code

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)

Output

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

---

Details

We use read_file to yield each line of the file.

find_longest_sequences builds a defaultdict that groups similar sequences together. It iterates the data with two loops:

1. The first loop builds a dict of empty lists with unique sequences as keys.
2. The second loop appends as values any strings that are similar to the key.

A set of the values is made of the resulting dict, and the longest sequences are returned.

Note some discrepancies with your expected output:

1. FGH overlaps with ABCDEFGHIJKLMNO and is thus not a valid output.
2. FEOEUDNBNUWD is not an original sequence. Post-processing is needed for overlapping sequences.

回答11:

As stated in other answers, your error comes from calculating the length of your input at the start and then not updating it as you shorten the list.

Here's another take at a working solution:

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