\documentclass[11pt]{article}
\usepackage{html}

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

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

\newcommand{\SPC}{\_}

\newcommand{\seq}[1]{\ensuremath{\mbox{\tt #1}}}

\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}}

\begin{document}
\begin{center}
{\large
Projeto de Biologia Computacional --- 2001
}
\vspace{0.7cm}

{\Large
 \textbf{Parte 2: Alinhamento Múltiplo}\vspace{2mm}\\
Prazo de entrega: 17 de outubro
}
\end{center}

\section{Descrição}
Nesta segunda parte, vamos implementar uma heurística para o
alinhamento de várias seqüências usando a pontuação SP.

\begin{itemize}
\item Implemente o algoritmo estrela, ou um algoritmo que faça
alinhamentos progressivos, ou alguma variação desses.
\begin{itemize}
\item Para o algoritmo estrela, lacunas nas extremidades não devem ser
penalizadas, mas abertura de lacunas sim. Tente minimizar o
comprimento total do alinhamento~\footnote{Por exemplo, para alinhar
as seqüências \seq{ACTGA}, \seq{ACTTGA} e \seq{ACTCGA}, os dois
  alinhamentos abaixo poderiam ser produzidos pelo algoritmo estrela:
\begin{center}
\begin{tabular}{cc}
Alinhamento 1 & Alinhamento 2 \\
         ACT\_\_GA     &    ACT\_GA\\
         ACTT\_GA      &     ACTTGA\\
         ACT\_CGA      &     ACTCGA
\end{tabular}
\end{center}
Note que os alinhamentos induzidos entre a primeira seqüência e cada
uma das outras é o mesmo para os dois alinhamentos. Mas o segundo
alinhamento deve ser preferido por ter comprimento total menor.}.
\item Para o algoritmo de alinhamentos progressivos,  descreva e
justifique, se necessário, quais recorrências foram usadas no cálculo
da matriz de programação dinâmica, incluindo as inicializações usadas.
\end{itemize}
\item Analise a complexidade de seu algoritmo para alinhar $k$ seqüências
   de comprimento no máximo $n$ em função de $k$, $n$ e $l$, o
   comprimento do alinhamento.
\item Teste o seu algoritmo com as seqüências usadas na Parte 1 do
   projeto. Olhe no site do \textit{European Molecular Biology Laboratory}
\htmladdnormallink{\texttt{ftp://ftp.ebi.ac.uk/pub/databases/embl/align/}}
{ftp://ftp.ebi.ac.uk/pub/databases/embl/align/}
e teste também o seu alinhamento com alguma seqüência de DNA escolhida de lá.
\end{itemize}

\section{O que Entregar}

\begin{itemize}
\item Seu programa. Você deve entregar por e-mail o seu programa
  fonte. Se o programa é em \texttt{C} padrão, não precisa me mandar
  mais nada. Caso contrário, me mande também por e-mail uma versão
  compilada do programa, dizendo para qual sistema operacional
  o programa foi compilado.

\item Relatório comentando o trabalho feito, contendo:
\begin{itemize}
\item comentários sobre o algoritmo que você implementou;
\item a análise do algoritmo;
\item comentários dos testes feitos.
\end{itemize}
\end{itemize}
\end{document} 

   


