magaiver

O algoritmo esta meio confuso Mas aí vai o algoritmo a ser realizado minha duvida esta na hora de achar a cadeia1 armazenada em um vetor dentro do vetor da cadeia 2 Projeto Genoma Nome do arquivo fonte: genoma.alg Um grande projeto mundial está em curso para mapear todo o material genético do ser humano: o Projeto Genoma Humano. As moléculas de DNA (moléculas que contêm material genético) podem ser representadas por cadeias de caracteres que usam um alfabeto de apenas 4(quatro) letras: ‘A’,‘C’, ‘T’ e ‘G’. Um exemplo de uma cadeia é: TCATATGCAAATAGCTGCATACCGA. Nesta tarefa você deverá produzir uma ferramenta muito utilizada no projeto Genoma: um programa que procura ocorrências de uma pequena cadeia de DNA (que vamos chamar de p) dentro de uma outra cadeia de DNA (que vamos chamar de t). Você deverá procurar dois tipos de ocorrência: a "direta" e a "complementar invertida". Uma ocorrência direta é quando a cadeia p aparece como sub-cadeia dentro de t. Por exemplo, se p = CATA e t = TCATATGCAAATAGCTGCATACCGA, então p ocorre na forma direta na posição 2 e na posição 18 de t. Uma ocorrência complementar invertida depende da seguinte correspondência entre as letras do DNA: ‘A’Û‘T’ e ‘G’ Û‘C’. "Complementar o DNA" significa trocar as letras de uma cadeia de DNA seguindo essa correspondência. Se complementarmos a cadeia CATA, vamos obter GTAT. Mas além de complementar, é preciso também inverter, ou seja, de GTAT obter TATG. E é esta cadeia que deverá ser procurada, no caso da ocorrência complementar invertida. Assim, se p e t são as mesmas cadeias do exemplo anterior, então p ocorre na forma complementar invertida na posição 4 de t. 1. Tarefa Sua tarefa é escrever um programa que, dadas duas cadeias p e t, onde o comprimento de p é menor ou igual ao comprimento de t, procura todas as ocorrências diretas e todas as ocorrências complementares invertidas de p em t. 2. Entrada de Dados Os dados de entrada contém vários conjuntos de teste. Cada conjunto de teste é composto por três linhas. A primeira linha contém dois inteiros positivos, M e N, sendo M £ N, que indicam respectivamente o comprimento das cadeias de DNA p e t, conforme descrito acima. A segunda linha do conjunto de teste contém a cadeia p, e a terceira linha contém a cadeia t, onde p e t são compostas utilizando apenas os caracteres ‘A’, ‘C’, ‘G’ e ‘T’. O final do arquivo de testes é indicado quando M = N = 0 (este último conjunto de testes não é válido e não deve ser processado). Os dados de entrada contêm ao menos um conjunto de teste que deve ser processado. Exemplo de Entrada 2 4 AC TGGT 4 25 CATA TCATATGCAAATAGCTGCATACCGA 0 0 3. Saída de Dados Seu programa deve produzir os dados de saída abaixo. Para cada conjunto de teste dos dados de entrada seu programa deve produzir quatro linhas no arquivo de saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. Na segunda linha deve aparecer a lista, em ordem crescente, com a posição inicial de cada ocorrência, na forma direta, do padrão p na seqüência t. Na terceira linha deve aparecer a lista, em ordem crescente, com a posição inicial de cada ocorrência, na forma complementar invertida, do padrão p na seqüência t. A quarta linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente. Exemplo de Saída Teste 1 ocorrência direta: 0 ocorrência complementar invertida: 3 Teste 2 ocorrência direta: 2 18 ocorrência complementar invertida: 4 (esta saída corresponde ao exemplo de entrada acima) algoritmo "semnome" // Função : // Autor : // Data : 15/8/2002 // Seção de Declarações var C, A, G, T, cadeia1, cadeia2: caracter M, N, testen,I,J,K,L,P,Q,cont: inteiro vetM: vetor [1..20] de caracter vetN: vetor [1..20] de caracter VetMI: vetor [1..20] DE caracter VetIN: vetor [1..20] de caracter inicio J<-0 K<-0 L<-0 Q<-0 escreval ("Informe o número de caracteres que conterá a primeira cadeia e a segunda cadeia, ou seja, o comprimento. ") leia (M, N) enquanto M>N faca escreval ("Entrada de dados incorreta. Digite novamente (a cadeia 1 deve ser menor ou igual a cadeia2") leia (M,N) fimenquanto Se (M<>0) e (N<>0) então Para I de 1 ate M faca escreval ("Digite a cadeia p. Deve conter apenas os caracteres A, C, G, T (informe uma letra e tecle enter). ") leia (cadeia1) J<-J+1 VetM[J]<-cadeia1 fimpara Para I de 1 ate N faca escreval ("Digite a cadeia t. Deve conter apenas os caracteres A, C, G, T. ") leia (cadeia2) K<-K+1 VetN[K]<-cadeia2 fimpara J<-0 L<-0 Para I de 1 ate M faca L<-L+1 J<-J+1 Se (vetM[J]="A") então vetMI[L]<-"T" senao Se (vetM[J]="T") então VEtMI[L]<-"A" senao Se (vetM[J]="C") então vetMI[L]<-"G" senao VetMI[L]<-"C" fimse fimse fimse fimpara P<-L Para I de 1 ate P faca Q<-Q+1 vetin[Q]<-vetmi[L] L<-L-1 fimpara fimalgoritmo