Quesito di calcolo combinatorio

*gregantony
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
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
*gregantony
up :(
plz

Rggb1
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,
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]

Umby2
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 $

*gregantony
Abbiamo fatto un passo avanti (e vi ringrazio per questo).
@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?)

Rggb1
in realtà credo sia maggiore (non minore). Ma a parte questo il ragionamento credo sia corretto, solo che non saprei formalizzarlo.

"mistypen" :-D
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.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.