C Como fazer esse programa em c

[Geovanecrawler]

Um k-mer é uma cadeia de caracters de tamanho k. Definimos a função count(T, P) como o número de vezes que o k-mer P ocorre como uma subcadeia do texto T. Por exemplo:

 

count(ACAACTATGCATACTATCGGGAACTATCCT, ACTAT) = 3

Dizemos que um padrão P é o k-mer mais frequente em um texto T se count(T, P) é máximo entre todos os k-mer de T. Por exemplo: "ACTAT é o 5-mer mais frequente de "ACAACTATGCATCACTATCGGGAACTATCCT", e "ATA" é o 3-mer mais frequente de "CGATATATCCATAG".

Problema das palavras frequentes

Encontre os k-mers mais frequentes de uma cadeia.

Entrada

Uma cadeia T e um inteiro k (tamanho da cadeia é no máximo 1024 caracteres).

Saída

Todos os k-mers mais frequentes (na ordem em que ocorrem em T, separados por um espaço em branco).

Exemplo

Entrada: ACGTTGCATGTCGCATGATGCATGAGAGCT 4 Saída: GCAT CATG

[arfneto]

Olá

 

Não que seja essencial mas, para não ter que escrever outra, entre as funções que manipulam strings em string.h  tem strstr()

que é declarada assim no seu caso

char * strstr ( const char* cadeia, const char* k-mer );

Ela devolve um ponteiro para a primeira ocorrência de k-mer na string, ou null.

 

E então você pode usar um loop para varrer a string de entrada variando os k-mer possíveis a partir do início e acumulando em uma tabela para mostrar no final. A cada sucesso você avança o ponteiro da string inicial para procurar adiante. Varrendo da esquerda para a direita eles já vão sair na ordem em sua tabela

 

 

[Geovanecrawler]

Obrigado, pela possível resolução do problema.

adicionado 1 minuto depois

#include <stdio.h> 
#include <string.h>

int main()
{
char str[1025];
char mer[100]; 
int i,j,k, cont = 0;
printf("Preencha a sequência: ");
fgets(str, 1025, stdin);
printf("Preencha a sequência: ");
fgets(mer, 100, stdin);
printf("Entre com um valor de k: "); 
scanf("%d", &k);
j = strlen(str);
for(i = 0; i <= k-1; i++)
mer = str;

for(i = 0; i <= j; i = i + k)
{
if(strcmp(str, mer) == 0)
cont++;
else
i = i + k;
}
printf("%d", cont);
return 0;
}

adicionado 2 minutos depois

Eu fiz assim, mas não resolveu o problema. Vou alterando e buscando solução.

[arfneto]

Recomendo mesmo usar strstr() e buscar o k-mer dentro da cadeia original e ir adiantando o ponteiro dela conforme for encontrando ocorrências. Experimente antes no papel por umas vezes...

 

Eu sempre recomendo o seguinte: não misture as coisas. Esqueça esse lance de ler a string e o k-mer de teste. Só vai perder tempo. Use por exemplo o  enunciado e não mexa enquanto não funcionar.

 

Depois em 5 minutos você coloca a leitura. 

[arfneto]

Olá!

Ainda sobre esse problema, count() é essencial para resolver isso, mais alguma rotina como a de que falei, strstr(). E o enunciado tem 3 exemplos com resposta...

Então escreva e teste cont() primeiro e teste com os valores do enunciado...

 

veja isso:

testando para 'ACAACTATGCATCACTATCGGGAACTATCCT' e 5-mer
Primeiro 5-mer em 'ACAACTATGCATCACTATCGGGAACTATCCT' = 'ACAAC'
Buscando 'ACAAC(5)' em 'ACAACTATGCATCACTATCGGGAACTATCCT(31)'
strstr() encontrou 'ACAAC' em 'ACAACTATGCATCACTATCGGGAACTATCCT' !!!!
count() retornou 0


testando para 'CGATATATCCATAG' e 3-mer
Primeiro 3-mer em 'CGATATATCCATAG' = 'CGA'
Buscando 'CGA(3)' em 'CGATATATCCATAG(14)'
strstr() encontrou 'CGA' em 'CGATATATCCATAG' !!!!
count() retornou 0
testando para 'ACGTTGCATGTCGCATGATGCATGAGAGCT' e 4-mer
Primeiro 4-mer em 'ACGTTGCATGTCGCATGATGCATGAGAGCT' = 'ACGT'
Buscando 'ACGT(4)' em 'ACGTTGCATGTCGCATGATGCATGAGAGCT(30)'
strstr() encontrou 'ACGT' em 'ACGTTGCATGTCGCATGATGCATGAGAGCT' !!!!
count() retornou 0

 

que o programa abaixo mostra a partir dos dados do exercício e já declarando count() e testo o primeiro k-mer de cada string com strstr()

 

#define     _CRT_SECURE_NO_WARNINGS

#include    <memory.h>
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>


// prototipos para referencia
int count(char*, char*);
int testa_count(char*, int);


int main(int argc, char** argv)
{
    // as cadeias do enunciado porque nao?
    char*        entrada1 = "ACAACTATGCATCACTATCGGGAACTATCCT";            // 5-mer "ACTAT"
    char*        entrada2 = "CGATATATCCATAG";                    // 3-mer "ATA"
    char*        entrada3 = "ACGTTGCATGTCGCATGATGCATGAGAGCT";    // 4-mer = "GCAT" e "CATG"

    testa_count(entrada1, 5);
    testa_count(entrada2, 3);
    testa_count(entrada3, 4);

    return 0;
}


int count(char* cadeia, char* kmer)
{
    // count() dee devolver o numero de vezes em que 
    // k-mer aparece em cadeia
    printf(
        "Buscando '%s(%d)' em '%s(%d)'\n", 
        kmer, strlen(kmer), 
        cadeia, strlen(cadeia)
    );
    char* pos = strstr(cadeia, kmer);
    if (pos == NULL)
        printf(    "Nao tem '%s' em '%s'\n", kmer, cadeia);
    else
        printf("strstr() encontrou '%s' em '%s' !!!!\n",
            kmer, cadeia);
    return 0;
}    // end count()


int testa_count(char* cadeia, int n_kmer)
{
    char    parte[80];
    printf("\n\ntestando para '%s' e %d-mer\n", cadeia, n_kmer);
    int l = strlen(cadeia);
    if (l < n_kmer) return -1;        // nao pode ser menor
    if (l == n_kmer) return 1;        // sao do mesmo tamanho!
    // monta em parte o primeiro k-mer possivel
    memcpy(parte, cadeia, n_kmer);
    parte[n_kmer] = 0;
    // ok: em 'parte' esta o primeiro valor
    printf("Primeiro %d-mer em '%s' = '%s'\n", n_kmer, cadeia, parte);
    // testa count()
    int n = count(cadeia, parte);
    printf("count() retornou %d\n", n);
    return 0;
}    // end testa_count()

e talvez ajude a entender o que estou falando: Use o que já tem e vá devagar

 

[Geovanecrawler]

Obrigado por fazer um exemplo de código. Vou ir fazendo o meu.

adicionado 0 minutos depois

Clareou bastante a ideia.

[arfneto]

Olá!

Mais palpites:

 

Considere que deve tratar ate 1024-mer, o que está no enunciado. Claro que nesse caso o resultado é óbvio.

 

Pensando no caso de uma cadeia "ABCDABCDABCD" e 3-MER para facilitar, temos os possíveis 3-mer a partir de ABC

00    ABCDABCDABCD
01    ABC
02     BCD
03      CDA
04       DAB
05        ABC
06         BCD
07          CDA
08           DAB
09            ABC
10             BCD

 Um 3-mer não pode iniciar antes da segunda posição simplesmente porque não cabe lá, certo? Então

Para uma cadeia de comprimento N temos um total de (N-(k-1)) possíveis k-mer

 Obviamente pode haver repetição, então podem ser menos que isso. Quanto menos? Simples: numa cadeia onde todas as posições são iguais temos um único k-mer --- "AAAAA" por exemplo.

 

Então uma função que, dada uma cadeia C e um inteiro K devolvesse uma lista de todos os k-mer sem repetição seira muito bem recebida. Somada à rotina count() obrigatória e mais uma tabela dá a solução para o problema, certo? Usando a lista de k-mers únicos chamamos count() e tabelamos os valores. Pegamos o maior --- ou maiores --- e pronto

Esse é um ponto importante: como o enunciado mostra um exemplo com repetição, não podemos apenas mostrar um dos máximos: vai ser preciso mostrar todos os k-mer que tem o comprimento máximo. Chato isso.

 

Saberia declarar essa função lista_k-mer()? 

adicionado 48 minutos depois

Olá!

 

Eis uma estrutura que pode funcionar para resumir cada pesquisa --- pode ajudar a construir o programa completo:

struct K_mer
{
    char*    k_mer;
    int      total;
};

struct Pesquisa
{
    char*            cadeia;
    unsigned short   k;            // 1024 max
    unsigned short   total_k_mer;    
    struct K_mer*    k_mer;
};
typedef struct Pesquisa pesquisa;

Assim a função de que falei só precisaria preencher essa estrutura...

Veja como podia declarar isso para os exemplos do enunciado

    // as cadeias do enunciado porque nao?
    char*        entrada1 = "ACAACTATGCATCACTATCGGGAACTATCCT";            // 5-mer "ACTAT"
    char*        entrada2 = "CGATATATCCATAG";                    // 3-mer "ATA"
    char*        entrada3 = "ACGTTGCATGTCGCATGATGCATGAGAGCT";    // 4-mer = "GCAT" e "CATG"

    pesquisa    p1;
    p1.cadeia = entrada1;
    p1.k = 5;
    p1.total_k_mer = 0;
    p1.k_mer = NULL;

    pesquisa    p2;
    p1.cadeia = entrada2;
    p1.k = 3;
    p1.total_k_mer = 0;
    p1.k_mer = NULL;

    pesquisa    p3;
    p1.cadeia = entrada3;
    p1.k = 4;
    p1.total_k_mer = 0;
    p1.k_mer = NULL;