Projeto de Python - montagem de trechos com interseção

versão 1

data de entrega 5/11 ate 8:00 da manha

Individual ou em grupos de até 3 pessoas.

Esse projeto reflete meu pouco entendimento do processamento para a montagem do genoma.

No processamento de genoma, a metodologia é quebrar o DNA em trechos (pequenos) , e sequenciar esses trechos. O problema deste projeto é montar o genoma de volta dado a sequencia dos trechos.

Vamos dizer que 2 trechos tem uma interseção se o final de um deles tem os mesmos componentes do começo do outro, e essa interseção tem 4 ou mais elementos.

Assim:

abcdefghij
fghijaaagguujj

tem interseção pois o final do primeiro fghij é exatamente igual ao começo do segundo trecho e o tamanho dessa parte em comum é maior ou igual a 4.

Já,

abcdefghij
hijxxxuuuvvv

não satisfazem o critério, pois a parte comum hij tem menos que 4 letras.

Voce deve ler de standard input varias linhas que indicam os vários trechos, numa ordem qualquer.

xxxxxababababyyyyyy
yyaaaaaaaaaaa
yyyyyyeeeeeeeeeeeeee
cccccccccccccccxxxxx
fffffffffffffffwwwwww
wwwwwwgggggggggggxx

O objetivo é montar as maiores sequencias permitidas pelos trechos, juntando, em ordem, os trechos que tem interseção.

Note que a linha 4 tem interseção com a linha 1, que tem intercessão com a linha 3, nesta ordem. Já a linha 5 tem interseção com a linha 6, nessa ordem, e a linha 2 não tem intercessão com nenhuma outra. Note que a parte comum de 2 trechos não precisa ser uma letra repetida; eu fiz isso neste exemplo para que as partes em comum ficassem visualmente claras.

Assim, com esses trechos, o máximo que podemos dizer é que o genoma é composto de 3 segmentos:

cccccccccccccccxxxxxababababyyyyyyeeeeeeeeeeeeee
fffffffffffffffwwwwwwgggggggggggxx
yyaaaaaaaaaaa

onde o primeiro segmento é a montagem da linha 4 com 1 com 3, o segundo a montagem da linha 5 com 6 a a terceira, o linha 2 apenas.

Escreva um programa em Python que le do standard input os vários trechos (um por linha), e imprime as sequencias resultantes da montagem dos trechos. As sequencias podem estar em qualquer ordem.

O projeto sera executado como:

python proj.py < trechos

O projeto deverá rodar com qq python >= 3.7 e so pode usar funções das bibliotecas padrão.