\documentclass[11pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[T1]{fontenc}
%----------------------------

\newtheorem{exercicio}{Exercício}
\usepackage{enumerate}

\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.5in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}
\setlength{\textwidth}{6.75in}
\pagestyle{empty}


\newcommand{\LINHA}{\noindent\hrulefill}

\newenvironment{alg}
{\begin{list}{\mbox{}}
{\setlength{\topsep}{0pt}
 \setlength{\parsep}{0pt}
 \setlength{\partopsep}{0pt}
 \setlength{\itemsep}{0pt}
 \setlength{\labelsep}{0pt}
 \setlength{\leftmargin}{3ex}
}}{\end{list}}

\usepackage{epsf}

\begin{document}
\begin{center}
{\large
MAC 5726 -- Biologia Computacional
}
 
\vspace{0.7cm}
 
Primeira lista de exercícios -- Entrega \textbf{13 de setembro de 1999}
\end{center}

\begin{exercicio} \rm \makebox[1mm]{}
%Gusfield 11.9.12
O \textit{Algoritmo Alinhamento} determina um alinhamento ótimo entre
dois strings $s$ e $t$.
Modifique o algoritmo para imprimir \textit{todos} os alinhamentos
ótimos.

Seu algoritmo deve gastar tempo $O(|s|+|t|)$ para imprimir cada
alinhamento. Explique porque isso é verdade.
\end{exercicio}

\begin{exercicio} \rm \makebox[1mm]{}
%Gusfield 11.9.14
Com um sistema de pontuação com $g=0$, $p(i,j)=1$
se $s[i]=t[j]$ e $p(i,j)=0$ se $s[i] \neq t[j]$, os símbolos alinhados
e iguais
num alinhamento ótimo formam uma \textit{subseqüência} comum a $s$ e a
$t$ de comprimento máximo.
Prove que isso é verdade.
Dê detalhes em como \textit{encontrar} a subseqüência.
\end{exercicio}

\begin{exercicio} \rm \textbf{(Tandem Repeats)} \makebox[1mm]{} \\
%Gusfield 11.9.32
Seja $P$ um padrão de comprimento $n$ e $T$ um texto de comprimento
$m$.
Seja $P^{m}$ a concatenação de $P$ com ele próprio $m$ vezes ($P^{m}$
tem comprimento $mn$).
Queremos computar um alinhamento local entre $P^{m}$ e $T$.
Com isso, encontraremos um intervalo em $T$ que tem o melhor
alinhamento global com alguma repetição do padrão $P$.

Este problema aparece no estudo de estruturas secundárias de proteínas
que formam a chamada \textit{coiled-coil}.
Naqule contexto, $P$ representa um \textit{motif} ou \textit{domínio}
que pode repetir na proteína um número desconhecido de vezes, e $T$
representa a proteína.

Um alinhamento local entre $P^{m}$ e $T$ escolhe um intervalo em $T$
que consiste ``otimamente'' de repetições seguidas de $P$.
Se $P^{m}$ é criado explicitamente, então o algoritmo de alinhamento
local resolve o problema em tempo $O(nm^{2})$.
Mas como $P^{m}$ consiste de $m$ cópias idênticas de $P$, um algoritmo
$O(nm)$ é possível.
O método consiste essencialmente em simular o que o algoritmo de
programação dinâmica faria se fosse executado com $P^{m}$ e $T$
  explicitamente.

O algoritmo de programação dinâmica irá preencher uma matriz $a$ com
$m+1$ linhas e $n+1$ colunas.
Linha $0$ e coluna $0$ são inicializadas com $0$'s.
Então, para cada linha $i$, o algoritmo faz o seguinte: executa o
algoritmo padrão para na linha $i$; atribui a $a[i,0]$ o valor de
$a[i,n]$ e executa novamente o algoritmo padrão para a linha $i$.
Depois de preencher cada linha, o algoritmo escolhe como resposta a
maior entrada de $a$.

Determine a complexidade desse algoritmo e prove que ele encontra
corretamente o valor do alinhamento ótimo entre $P^{m}$ e $T$.
Dê detalhes de como encontrar o alinhamento ótimo local.
Discuta porque $P$ foi expandido (conceitualmente) para $P^{m}$ e não
para um string maior ou menor.
\end{exercicio}

\begin{figure}
\begin{center}
\epsffile{tRNA.eps}
\end{center}
\caption{\label{tRNA} Representação de um pareamento aninhado}
\end{figure}

\begin{exercicio} \rm \textbf{(The tRNA folding problem)} \makebox[1mm]{} \\
%Gusfield 11.9.41
Esta é uma versão bastante primitiva do problema da predição da estrutura
secundária (planar) do tRNA.
Seja $s$ um string de $n$ caracteres representando um tRNA.
Definimos um \textit{pareamento} como um conjunto de pares disjuntos
de $s$. Um pareamento é chamado \textit{próprio} se ele contém somente
pares $\{A,U\}$ ou $\{C,G\}$, ou seja, somente pares de nucleotídeos
complementares.
Se desenharmos $s$ como um string circular, definimos como pareamento
\textit{aninhado} um pareamento próprio onde cada par no pareamento é
ligado por um segmento de linha dentro do círculo, e onde os segmentos
não se cruzam (ver Figura~\ref{tRNA}).
O problema é encontrar um pareamanto aninhado de maior cardinalidade.
Mostre como resolver este problema em tempo $O(n^3)$.

Agora, modifique o problema adicionando pesos aos pares: o peso de um
par $\{A,U\}$ é diferente do peso de um par $\{C,G\}$.
O objetivo agora é encontrar um pareamento aninhado de peso total
máximo.
Dê um algoritmo eficiente para este problema.
\end{exercicio}

\begin{exercicio} \rm \makebox[1mm]{} \\
Implemente um dos seguintes algoritmos.
\begin{enumerate}
\item Dados strings $s$ e $t$, calcular o alinhamento entre eles
  usando espaço $O(|s|+|t|)$.
\item Dados strings $s_{1}, s_{2}, \ldots, s_{k}$, calcular o valor do 
  alinhamento múltiplo ótimo entre eles.
\end{enumerate}
Mande um e-mail para mim dizendo como faço para acessar ou copiar ou
compilar seu programa.
\end{exercicio}

\end{document} 

