Predictor de patologies P90639

Donat un alineament múltiple de seqüències de proteïnes, esbrineu si la mutació de l’amino àcid $x$ a l’amino àcid $y$ a la posició $p$ és patològica. Per fer-ho, compteu quants cops apareixen tant $x$ com $y$ a la posició $p$ de l’alineament. Siguin $n_x$ i $n_y$ aquestes quantitats. Si $2n_y \ge n_x$, considerarem que la mutació és neutral; altrament, la catalogarem com a patològica.

Breu explicació biològica

En l’alineament múltiple, trobem proteïnes similars–humanes o d’altres espècies–alineades, contraposant a cada aminoàcid l’aminoàcid equivalent en les altres proteïnes. Donada una mutació $x \rightarrow y$ a la posició $p$, podem suposar que si l’aminoàcid $y$ apareix en la posició $p$ en poques seqüències de l’alineament, això vol dir que aquest aminoàcid no podrà realitzar la mateixa funció que l’original en aquesta posició. En canvi, si l’aminoàcid $y$ apareix almenys la meitat de vegades que $x$, entenem que sí que és capaç de complir la mateixa funció, i que per tant la mutació és neutral.

Entrada

L’entrada comença amb $n$, el nombre de línies de l’alineament. Segueixen les $n$ línies, totes de la mateixa amplada $a$, només amb aminoàcids i guions. La primera d’aquestes línies es correspon a la proteïna original, i no té guions. Després ve $m$, el nombre de mutacions a estudiar, seguit de $2m$ línies. Cada dues línies descriuen una consulta, amb la posició $p$ (començant en 1), i l’amino àcid mutat $y$. Implícitament, l’amino àcid $x$ és el que es troba a la posició $p$ de la proteïna original.

Suposeu $2 \le n \le 1000$, $1 \le a \le 1000$, $1 \le m \le 1000$, $1 \le p \le a$, i que $x$ i $y$ són dos aminoàcids diferents. Cada aminoàcid es codifica amb una lletra majúscula escollida entre “ACDEFGHIKLMNPQRSTVWY”.

Sortida

Escriviu $m$ línies, una per consulta, amb “neutral” o “patologica” (sense accent), segons convingui.