python - biologists - Eliminar elemento de la lista en función del siguiente elemento de la misma lista

biopython install

Question

Acabo de comenzar a aprender python y aquí tengo una lista ordenada de secuencias de proteínas (59.000 secuencias en total) y algunas de ellas se superponen. He hecho una lista de juguetes aquí por ejemplo:

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

Me gustaría eliminar esas superposiciones más cortas y simplemente mantener la más larga para que la salida deseada se vea así:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
FEOEUDNBNUWD
FGH

¿Cómo puedo hacerlo? Mi código se ve así:

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

Y recibí el mensaje de error:

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

Answer 1

Como se indicó en otras respuestas, su error proviene de calcular la longitud de su entrada al inicio y luego no actualizarla a medida que acorta la lista.

Aquí hay otra toma de una solución de trabajo:

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

Answer 2

Esto te llevará a donde quieras estar:

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

He añadido set en caso de múltiples apariciones del mismo texto.

Answer 3

Hay otras respuestas de trabajo, pero ninguna de ellas explica su problema real. En realidad, estabas realmente cerca de una solución válida y, en mi opinión, la respuesta más fácil de leer.

El error provino del hecho de que estaba mutando la misma lista mientras comprobaba el índice usando range() .

Por lo tanto, al aumentar la variable i , estaba eliminando el elemento de la lista, lo que en un punto provoca el index error inevitablemente.

Por lo tanto, aquí hay una versión de trabajo de su código inicial con algunos cambios,

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

Tenga en cuenta que este código funcionará si su lista se clasificó previamente como mencionó en la sección de comentarios.

¿Qué está haciendo este código?

Básicamente, usa la misma lógica de su respuesta inicial donde itera en la lista y verifica si el siguiente elemento contiene el elemento actual. Pero, usar otra lista e iterar hasta el último elemento anterior, solucionará su problema de índice. Pero ahora viene una pregunta,

¿Qué debo hacer con el último artículo?

Dado que la lista está ordenada, puede considerar que el último elemento siempre es único . Por eso estoy usando

output_pattern.append(pattern[-1])

que agrega el último elemento de la lista inicial.

Nota IMPORTANTE

Esta respuesta se escribió en respuesta a la pregunta inicial de OP en la que quería mantener la superposición más larga y cito según el siguiente elemento de la misma lista . Como lo indica @Chris_Rands, si sus inquietudes están relacionadas con una tarea biológica y necesita encontrar alguna superposición, esta solución no es adecuada para sus necesidades.

Ejemplo en el que este código no reconocería una posible superposición,

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

donde se obtendría el mismo resultado sin eliminar la posible superposición de "ACD" . Ahora, solo como una aclaración, esto implicaría un algoritmo mucho más complejo e inicialmente pensé que estaba fuera del alcance de los requisitos de la pregunta. Si este es su caso, es posible que esté completamente equivocado aquí, pero realmente creo que una implementación de C ++ parece más apropiada. Eche un vistazo al algoritmo de CD-Hit sugerido por @Chris_Rands en la sección de comentarios.

Answer 4

Kenny, casi lo entiendes, pero hay dos problemas que @scharette señaló:

1. for bucle y eliminación de elemento de la lista no debe ir juntos. La solución es utilizar el bucle while y aumentar explícitamente el índice. El bucle while es menos eficiente porque llama a len() varias veces en lugar de una vez, pero eso es lo que se necesita para obtener el resultado correcto.
2. El IndexError . Esto solo sucede en la última línea. Mi manera de lidiar con este problema es ignorar el error.

Con eso, modifiqué tu código para:

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

Answer 5

No coincide exactamente con sus expectativas, pero, dado que usted EOEUDNBNUWD EAEUDNBNUW que está ordenado (y no lo está, está cerca de EOEUDNBNUWD EAEUDNBNUW ) y que no sé por qué falta EOEUDNBNUWD no estoy seguro de si sus expectativas están expresadas correctamente o si He leído mal tu pregunta.

(Ah, sí, veo que la noción de superposición arroja una llave en la sort y startswith acercarse).

Puede ser bueno que el OP replantee ese aspecto en particular, leí el comentario de @DSM sin entender realmente su preocupación. Ahora lo hago.

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)

salida:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EAEUDNBNUW
EOEUDNBNUWD
FEOEUDNBNUW
FGH

Answer 6

Puede usar groupby() y max() para ayudar aquí:

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

Esto mostraría:

ABCDEFGHIJKLMNO
CEST
DBTSFDEO
EOEUDNBNUW
EAEUDNBNUW
FGH

groupby() funciona devolviendo una lista de elementos coincidentes en función de una función, en este caso líneas consecutivas con los mismos primeros 2 caracteres. La función max() toma esta lista y devuelve el elemento de la lista con la longitud más larga.

Answer 7

Puede usar un árbol binario cuyo proceso de inserción intente encontrar nodos que preceden al valor:

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

Salida:

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

Answer 8

Una forma simple es procesar el archivo de entrada una línea a la vez, comparar cada línea con la anterior y mantener la anterior si no está contenida en la actual.

El código puede ser tan simple como:

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

Answer 9

Código

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)

Salida

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

Detalles

Usamos read_file para producir cada línea del archivo.

find_longest_sequences crea un find_longest_sequences que agrupa secuencias similares. Se itera los datos con dos bucles:

1. El primer bucle crea un dict de listas vacías con secuencias únicas como claves.
2. El segundo bucle agrega como valores a las cadenas que son similares a la clave.

Se crea un conjunto de valores del dictado resultante y se devuelven las secuencias más largas.

Note algunas discrepancias con su salida esperada:

1. FGH solapa con ABCDEFGHIJKLMNO y, por lo tanto, no es una salida válida.
2. FEOEUDNBNUWD no es una secuencia original. El posprocesamiento es necesario para las secuencias superpuestas.

Answer 10

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

Salida:

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

Answer 11

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)

Salida

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