Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

EDUPT09 - Crossing over

A análise genômica teve avanços significativos nessa última década, culminando com o completo mapeamento do genoma humano.

       

 

      
 


Um processo que os geneticistas gostariam de dominar no laboratório é a de crossing-over. Trata-se de um fenômeno, que ocorre durante a meiose, é que consiste na quebra de cromossomos em alguns pontos e, na sequência, há uma troca de pedaços correspondentes entre eles. Vale destacar ainda que as trocas provocam o surgimento de outras sequências de genes ao longo dos cromossomos, como mostram as figuras a seguir.

 

Um grupo de geneticistas está muito interessado em simular o crossing-over, para tentar prever todas as caraterísticas possíveis. Nessa simulação um gene é uma sequência de bases do DNA (Adenina, Citosina, Guanina, Timina).

A ideia desses cientistas é controlar o crossing-over, localizando uma sequência de bases genéticas e substituindo por outra sequência, todas as vezes que um par dessas sequencias ocorrerem nos genes.

Você foi contratado para realizar essa simulação. Há muitas formas de armazenar os dados gerados por esse mapeamento, mas uma das formas mais eficientes de manipular as bases é tratar cada gene como uma lista encadeada de bases de DNA na ordem que parecem no gene.

Para sua simulação, os cientistas informam dois genes (ou pedaços de genes) e quais sequencias devem ser trocadas entre esses genes.  e você deve mostrar as duas novas sequências geradas. Para essa simulação, os pares de sequências devem ser trocados todas as vezes que forem encontrados e as trocas ocorrem na ordem em que são informadas.

ENTRADA

A primeira linha contém a sequência do primeiro gene, nessa simulação, um gene pode ter até 103 bases.

A segunda linha contém a sequência do segundo gene.

A terceira linha contém o número de pares de sequencias para troca. 

Os próximos pares de linhas contêm as sequencias que devem ser trocadas entre si nos dois genes.

 

SAÍDA

A primeira linha contém a nova sequência do primeiro gene.

A segunda linha contém a nova sequência do segundo gene.

 Exemplos 

Entrada

 

SAÍDA

 

ACTGACTGCG

GCTGGCCGGGTA

1

CT

 

GG

 

 

AGGGAGGGCG

GCTCTCCCTGTA

 

 

GCTAATACG
ATTGTTGCT
GCTAATACG
ATTGTTGCT

 

1

TA

TGT

 
GCTGTATACG
ATTATGCT

 

GCGGGG

GGGTAC

1

AG

AC

 

GCGGGG

GGGTAC

 

TGCTAATACGGAT

CAATGTTGCTGCC

3

AAT

CAATG

AAT

GC

GAC

TCG

 

TGCTCGCTCGGGAT

AATTTAATGACC

 

TGCTAATACGGATCGCGGGGAGAACAAAGGATCAGTTTACTATGATCAGAAACCAGCCCGCTTTACAGTGCTCGCTAGTCAA

CATTGTTGCTGCCCGGGATCACTAACGTCACAAGCCCACGGCGTGTAGGAGTGAATATCCCCATCTGGGGGATTCC

1

TCGCG

GGAT

TGCTAATACGGAGGATGGGAGAACAAAGGATCAGTTTACTATGATCAGAAACCAGCCCGCTTTACAGTGCTCGCTAGTCAA

CATTGTTGCTGCCCGTCGCGCACTAACGTCACAAGCCCACGGCGTGTAGGAGTGAATATCCCCATCTGGGGGATTCC

 

 
Submit solution!
Added by:IFTM_Maratona
Date:2022-10-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C
hide comments
2022-10-20 16:11:00
#include <stdlib.h>
#include <stdio.h>

struct no
{
int info;
struct no* prox;
};
typedef struct no No;

struct nod
{
int info;
struct nod* prox;
struct nod* ant;
};
typedef struct nod Nod;

struct listad
{
Nod* ini;
Nod* fim;
};
typedef struct listad Listad;

Listad* cria_listad()
{
Listad* novalista;
novalista = (Listad *)malloc(sizeof(Listad));
novalista->ini = novalista->fim = NULL;
return novalista;
}
Nod* cria_nod(void* valor)
{
Nod* novo = (Nod*)malloc(sizeof(Nod));
novo->ant = novo->prox = NULL;
novo->info = valor;
return novo;
}
Listad* insere_inicio_listad(Listad *L, void* valor)
{
Nod *novo= cria_nod(valor);

if (L == NULL)
{
L = cria_listad();
L->ini = L->fim = novo;
}
else
{
if (L->ini == NULL)
L->ini = L->fim = novo;
else
{
novo->prox = L->ini;
L->ini->ant = novo;
L->ini = novo;
}
}
return L;
}
Listad* insere_fim_listad(Listad* L, void* valor)
{
Nod *novo = cria_nod(valor);

if (L == NULL)
{
L = cria_listad();
L->ini = L->fim = novo;
}
else
{
if(L->ini == NULL)
{
L->ini = L->fim = novo;
}
else
{
novo->ant = L->fim;
L->fim->prox = novo;
L->fim = novo;
}
}
return L;
}
void* remove_inicio_listad(Listad *L)
{
Nod* aux;
void* resposta = NULL;//quando nao tem nada pra remover
if (L!=NULL)
if (L->ini != NULL)
{
aux = L->ini;

if (L->ini != L->fim)
{
L->ini->prox->ant = NULL;
L->ini = L->ini->prox;
}
else
L->ini = L->fim = NULL;

resposta = aux->info;
free(aux);
}
return resposta;
}
void* remove_fim_listad(Listad *L)
{
Nod* aux;
void* resposta = NULL;

if(L != NULL && L->fim != NULL)
{
aux = L->fim;
if(L->ini != L->fim)//mais de um elemento na lista
{
L->fim->ant->prox = NULL;
L->fim = L->fim->ant;
}
else//so tem um elemento na lista
L->ini = L->fim = NULL;

resposta = aux->info;
// free(aux);
}
return resposta;
}
Listad* libera_listad(Listad *L)
{
Nod *aux = L->ini;

while (aux != NULL)
{
L->ini = L->ini->prox;
free(aux);
aux = (Nod*)L;
}

free(L);
return NULL;

}
Listad* divide_lista(Listad *L, int nro_elementos)
{
Nod *aux = L->ini;
Listad *L2 = cria_listad();
while (nro_elementos > 0)
{
aux = aux->prox;
nro_elementos--;
}
L2->ini = aux;
L2->fim = L->fim;
L->fim = aux->ant;
L->fim->prox = NULL;
L2->ini->ant = NULL;

return L2;
}
No* cria_no(int valor)
{
//alocar um nó
No* novo = NULL;
novo = (No*) malloc (sizeof(No));
//inicializar campos
novo->prox = NULL;
novo->info = valor;
return novo;
}

No* insere_inicio(No* L, int valor)
{
No* novo;
if (L ==NULL)
{
L = cria_no(valor);
}
else
{
novo = cria_no(valor);
novo->prox = L;
L = novo;
}
return L;
}
No* insere_fim(No* L, int valor)
{
No* novo = cria_no(valor);
No* cont = L;

if (L == NULL)
L = novo;
else
{
while(cont->prox!=NULL){
cont=cont->prox;
}
cont->prox=novo;

}
return L;
}
void mostraL(No*L)
{
No* cont=L;
while(cont!=NULL){
printf("%d ",cont->info);
cont=cont->prox;
}
printf("\n");
}

int main()
{
int i=0, n=0, entrada=0;
Nod* ND;
Listad* LD;

printf("Quantidade de linhas: ");
scanf("%d", &n);

printf("Insira suas %d bases: \n");

for(i=0;i<n;i++){
if(entrada!=0){
scanf("%c",&entrada);
LD=insere_fim_listad(Listad* LD, void* entrada);
}

}
return 0;
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.