Quesito di calcolo combinatorio
Eccovi un piccolo quesito che avrei bisogno di risolvere per la mia tesi di laurea, ma io non sono in grado. Voi sapreste aiutarmi?
Andiamo subito al problema:
un allineamento tra due sequenze di caratteri (es: x=scomodi e y=condomino)
è qualcosa del tipo
cioè, si introducono dei gap(-) in ogni sequenza, in modo da accoppiare il maggior numero di caratteri possibile (qui abbiamo accoppiato CO-CO, D-D e I-I).
Non ci sono vincoli nel modo in cui si inserisce un gap, a parte che non è consentito far corrispondere due gap (perché non avrebbe senso). Ad esempio, l'allineamento:
non è consentito perché in seconda posizione c'è un gap in entrambe le sequenze (il che non ha senso).
Tutti gli altri allineamenti sono consentiti, quindi anche
oppure
che sono dei pessimi allineamenti, ma sono comunque degli allineamenti validi.
LA DOMANDA E'
sapendo la lunghezza di x e di y, come si esprime il numero di tutti i possibili allineamenti?
Penso che il ragionamento da applicare qui passi attraverso l'osservazione che il numero di gap nella stringa x variano da
$|y|-|x| <= $#GAP_in_x $<= |y|$
però non saprei andare oltre.
Grazie dell'aiuto,
ciao!
Andiamo subito al problema:
un allineamento tra due sequenze di caratteri (es: x=scomodi e y=condomino)
è qualcosa del tipo
x*: scomod--i-- y*: -con-domino
cioè, si introducono dei gap(-) in ogni sequenza, in modo da accoppiare il maggior numero di caratteri possibile (qui abbiamo accoppiato CO-CO, D-D e I-I).
Non ci sono vincoli nel modo in cui si inserisce un gap, a parte che non è consentito far corrispondere due gap (perché non avrebbe senso). Ad esempio, l'allineamento:
s-comod--i-- --con-domino
non è consentito perché in seconda posizione c'è un gap in entrambe le sequenze (il che non ha senso).
Tutti gli altri allineamenti sono consentiti, quindi anche
scomodi--------- -------condomino
oppure
scomodi-- condomino
che sono dei pessimi allineamenti, ma sono comunque degli allineamenti validi.
LA DOMANDA E'
sapendo la lunghezza di x e di y, come si esprime il numero di tutti i possibili allineamenti?
Penso che il ragionamento da applicare qui passi attraverso l'osservazione che il numero di gap nella stringa x variano da
$|y|-|x| <= $#GAP_in_x $<= |y|$
però non saprei andare oltre.
Grazie dell'aiuto,
ciao!
Risposte
up 
plz

plz
Partiamo dall'inizio. Ho una stringa $X$ di $h$ caratteri e una stringa $Y$ di $k$ caratteri.
La lunghezza massima delle sequenze di allineamento (che hanno uguale lunghezza per definizione) è a quanto ho capito $L=h+k$. La lunghezza minima è viceversa il numero $l$, uguale al minore fra $h$ e $k$.
Si vuole determinare tutte le sequenze possibili. Direi di partire considerando il numero di caratteri "non gap" appaiati, partendo proprio dal "caso limite" dove il numero di caratteri appaiati è zero,
(sequenza lunga $h+k$ caratteri) e poseguire appaiando un solo carattere
(sequenza lunga $h+k-1$ caratteri) e contando tutti i modi, poi appaiando due caratteri e così via. Vediamo dove ci porta il ragionamento, magari ci viene in mente un metodo più semplice.
[Modificato, c'era un errore nell'esempio]
La lunghezza massima delle sequenze di allineamento (che hanno uguale lunghezza per definizione) è a quanto ho capito $L=h+k$. La lunghezza minima è viceversa il numero $l$, uguale al minore fra $h$ e $k$.
Si vuole determinare tutte le sequenze possibili. Direi di partire considerando il numero di caratteri "non gap" appaiati, partendo proprio dal "caso limite" dove il numero di caratteri appaiati è zero,
xxxxx----- -----yyyyy
(sequenza lunga $h+k$ caratteri) e poseguire appaiando un solo carattere
xxxxx---- ----yyyyy xxxxx---- ---y-yyyy ... xxxxx---- y----yyyy xxxx-x--- ---yy-yyy ... xxxx-x--- y---y-yyy ...
(sequenza lunga $h+k-1$ caratteri) e contando tutti i modi, poi appaiando due caratteri e così via. Vediamo dove ci porta il ragionamento, magari ci viene in mente un metodo più semplice.
[Modificato, c'era un errore nell'esempio]
Non facile come quesito.
In quanti modi posso disporre i gap (-), considerato che le lettere devono essere comunque essere disposte in sequenza (ovvero non posso scambiarle tra loro)
Se ho ad esempio:
CASA
BAR
abbiamo detto che al massimo possiamo avere 7 posti, quindi
[CASA---]
in quanti modi posso disporre i 3 gap, nei 7 posti ?
$((7),(3)) = 35 $
per la seconda parola (BAR) sarà lo stesso
$((7),(4)) = 35 $
In quanti modi posso disporre i gap (-), considerato che le lettere devono essere comunque essere disposte in sequenza (ovvero non posso scambiarle tra loro)
Se ho ad esempio:
CASA
BAR
abbiamo detto che al massimo possiamo avere 7 posti, quindi
[CASA---]
in quanti modi posso disporre i 3 gap, nei 7 posti ?
$((7),(3)) = 35 $
per la seconda parola (BAR) sarà lo stesso
$((7),(4)) = 35 $
Abbiamo fatto un passo avanti (e vi ringrazio per questo).
@Rggb, quando dici:
Riguardo l'osservazione di Umby invece...
Consideriamo l'esempio BAR-CASA. Restringiamo il problema, per semplicità, al caso in cui il numero di gap è sempre 4 per BAR e 3 per CASA. Poi cercheremo di generalizzare.
Sappiamo adesso che le combinazioni di BAR (con 4 GAP) sono $((7) , (4))=35$
mentre quelli di CASA (con 3 GAP) sono $((7),(3))=35$
Gli allineamenti possibili sono quindi $35*35=1225$
A questi però adesso bisogna togliere quelli non consentiti, che sono quelli in cui i gap si sovrappongono.
Ad esempio il seguente allineamento non va bene, nonostante attualmente noi lo stiamo contando
Qualche idea?
(probabilmente l'approccio di Rggb è il prossimo passo, no?)
@Rggb, quando dici:
La lunghezza minima è viceversa il numero l, uguale al minore fra h e k.in realtà credo sia maggiore (non minore). Ma a parte questo il ragionamento credo sia corretto, solo che non saprei formalizzarlo.
Riguardo l'osservazione di Umby invece...
Consideriamo l'esempio BAR-CASA. Restringiamo il problema, per semplicità, al caso in cui il numero di gap è sempre 4 per BAR e 3 per CASA. Poi cercheremo di generalizzare.
Sappiamo adesso che le combinazioni di BAR (con 4 GAP) sono $((7) , (4))=35$
mentre quelli di CASA (con 3 GAP) sono $((7),(3))=35$
Gli allineamenti possibili sono quindi $35*35=1225$
A questi però adesso bisogna togliere quelli non consentiti, che sono quelli in cui i gap si sovrappongono.
Ad esempio il seguente allineamento non va bene, nonostante attualmente noi lo stiamo contando
BAR---- CASA---
Qualche idea?
(probabilmente l'approccio di Rggb è il prossimo passo, no?)
in realtà credo sia maggiore (non minore). Ma a parte questo il ragionamento credo sia corretto, solo che non saprei formalizzarlo.
"mistypen"

Gli allineamenti possibili sono quindi $35*35=1225$
A questi però adesso bisogna togliere quelli non consentiti, che sono quelli in cui i gap si sovrappongono.
Tralascio per ora il conteggio usando la combinatoria, voglio prima trovare la regola "grezza" e poi applicarla con una formula. Per l'esempio che ho postato:
- c'è un solo modo di allineare le parole quando nessun carattere è appaiato;
fino a qui, semplice. Ora passo a contare gli allineamenti con un carattere "appaiato" - uso questo termine che spero ci aiuti ad evitare confusione.
In pratica lo imposto come un algoritmo: "sposto" il primo carattere della seconda stringa di modo sia appaiato con l'ultimo della prima, con il penultimo e così via fino al primo; ripeto queste operazioni per tutte le combinazioni di lettere e gap della prima stringa (v. calcolo di Umby), di cui conosco la lunghezza.
Sto cercando di contare il totale dei modi in cui la prima e seconda stringa hanno un carattere appaiato, una regola che mi permetta di calcolarlo e una regola che permetta di estendere il calcolo appaiando tutti i caratteri possibili, via via fino al massimo.
Spero sia un metodo valido e soprattutto generalizzabile. Magari però c'è un sistema più semplice.