Disciplina de Biologia Computacional

Professor: Dr. João Meidanis

Assunto: Strings, Grafos e Algoritmos

Livro-texto: Capítulo 2 de Introduction to Computational Molecular Biology – SETUBAL, J. C.; MEIDANIS, J.

Strings

1. O que é uma string?

É uma concatenação sucessiva de símbolos.

2. Quantos símbolos são utilizados para representar o DNA?

É utilizado um alfabeto de 4 símbolos (A,C,G,T).

Obs 1: Por vezes, o símbolo N é utilizado para designar que numa determinada posição, a base não é conhecida.

Obs 2: A IUPAC (International Union of Pure and Applied Chemistry) define um conjunto de letras para representar bases e aminoácidos, bem como qualquer ambigüidade.

3. Qual a diferença entre subseqüência e substring?

A substring é formada por símbolos consecutivos da string/seqüência original.

A subseqüência pode ser formada por partes não consecutivas da string/seqüência original.

4. O que é um prefixo e um sufixo de uma string/seqüência?

Prefixo é uma substring no início da string.

Sufixo é uma substring no final da string.

Exemplos: dada a string ABCD, ABC é um prefixo de tamanho 3 e CD é um sufixo de tamanho 2.

Grafos

1. O que é um grafo?

É um conjunto de vértices e um conjunto de arestas ligando estes vértices.

2. Qual a diferença entre grafo orientado e não orientado?

No grafo orientado as arestas são definidas com orientação.

3. O que é um subgrafo e um subgrafo induzido?

Dado um grafo A, um subgrafo de A é um grafo cujos vértices e arcos são também arcos e vértices de A.

Um subgrafo G´ de G é induzido se todos os arcos entre os vértices de G que estão presentes em G´ também estão presentes em G´.

4. O que é componente conexo de um grafo?

É um subgrafo onde para quaisquer 2 de seus vértices existe um caminho de um para o outro.

Obs: Por vezes, o termo componente conexo é utilizado para o conjunto de vértices do subgrafo e não para o subgrafo propriamente dito.

5. O que é um componente fortemente conexo?

Este conceito só faz sentido em grafos orientados. Analogamente à questão anterior, é um subgrafo orientado onde para quaisquer 2 de seus vértices existe um caminho de um vértice para o outro. Observe que o caminho obedece à orientação dos arcos.

6. O que é uma árvore?

É um grafo acíclico e conexo.

7. O que é uma folha de árvore?

Para um árvore sem raíz, folhas são vértices com grau 1.

Para uma árvore com raíz, folhas são vértices com grau 1, a menos da própria raíz se esta possuir grau 1.

(*) O que é menor ancestral comum, não é a própria raíz?

Menor ancestral comum entre dois vértices é o ancestral comum mais profundo.

8. O que é um grafo de intervalos?

É um grafo onde os vértices correspondem a intervalos em R e os arcos são definidos pela existência de interseção entre intervalos (vértices do grafo).

9. O que é um grafo euleriano?

É um grafo que admite um ciclo passando por todos os seus vértices e arestas, sendo que cada aresta é transpassada uma única vez.

Obs: É fácil reconhecer um grafo euleriano? Sim. Basta verificar se o grafo é conexo e se todos os nós tem grau par. Essa condição é necessária e suficiente.

10. O que é um grafo hamiltoniano?

É um ciclo que passa por todos os vértices exatamente uma vez.

11. Qual a relação entre o problema do caixeiro viajante e o grafo hamiltoniano?

O grafo associado ao problema do caixeiro viajante apresenta duas diferenças básicas com relação ao grafo hamiltoniano. Primeiro, as arestas tem peso. Segundo, é sempre assumido um grafo completo, assumindo-se peso infinito para os arcos inexistentes. O problema consiste em encontrar o ciclo de menor peso e passando por todos os nós. Observe que um grafo completo admite ciclo hamiltoniano (arcos com peso 1). O problema do caixeiro viajante é NP-difícil e o problema de encontrar o ciclo hamiltoniano é NP-completo.

Algoritmos

1. O que é um algoritmo?

É uma seqüência de passos bem definida e finita usada para resolver um problema bem definido.

Obs 1: definir algoritmo formalmente é uma tarefa difícil. Alguns exemplos de formalismos incluem funções recursivas (computáveis), máquinas de Turing, RAM, dentre outras.

Obs 2: Em geral, associado a uma definição formal de algoritmo existe um dispositivo computável universal (ex: máquinas de Turing universais, funções recursivas universais, etc.).

2. Como se mede o tempo usado por um algoritmo?

Conta-se o número de operações básicas utilizadas para se executar o algoritmo. O número de operações é dependente da entrada.

E qual parâmetro usar para comparar as entradas? O tamanho da entrada.

Entradas diferentes do mesmo tamanho tem tempos de execução diferentes. Qual tempo considerar? Pode-se considear o tempo médio, mas via de regra, considera-se o maior (pior caso).

Esses valores exatos são difíceis de se determinar. O que se utiliza são estimativas de limitantes superiores (cotas).

3. O que é um algoritmo polinomial?

É um algoritmo que tem função de tempo de execução polinomial (o limite superior para o tempo de execução do algoritmo é uma função polinomial do tamanho da entrada).

4. O que é um problema da classe P?

É um problma para o qual existe um algoritmo de tempo polinomial para resolvê-lo.

5. O que é um problema NP?

É um problema para o qual existe uma máquina de Turing não determinística que o resolve em tempo polinomial. De forma equivalente, um problema pertence à classe NP se, uma vez obtida a solução, esta pode ser checada em tempo polinomial.


6. O que é um algoritmo não determinístico?