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

versão 1

Data de entrega: 22/10 até as 8:00 via email.

Individual ou em grupos de dois.

Esse projeto reflete meu pouco entendimento do processamento para a montagem do genoma (na tecnologia de 2005).

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 coma 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 Prolog 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 me qualquer ordem.

O projeto sera executado como

swipl -q -g main proj2.pl < trechos

ou seja o predicado principal do seu programa deve se chamar main, e a leitura dos trechos deve ser do standard input.