Problema con il calcolo di una probabilità

[fairyvilje]

Salve a tutti, ho un problema con il calcolo di una probabilità. A priori non so se esista una soluzione "chiusa" perché è un problema venuto fuori con la scrittura della mia tesi. In breve sto costruendo un modello probabilistico per le operazioni di sequenziamento del DNA e mi serve calcolare le probabilità di certi eventi per costruire un algoritmo ottimo. Uno di questi mi sta facendo impazzire.

Assumo di avere una stringa di DNA di lunghezza ovvero una stringa in con . Considero una finestra di lettura casuale con lunghezza fissa sul DNA, con la sua posizione di inizio.
Considero ora un vettore ordinato di letture, dove per ordine si intende la relazione d'ordine dei naturali tra i vari . La lunghezza di questo vettore è ovvero il numero di finestre considerate.
Voglio ora verificare la probabilità che un certo numero di finestre scelte casualmente sia sufficiente ad evitare caratteri non coperti. Il modo che mi è parso più semplice è stato considerare la distanza fra il punto di inizio fra ogni finestra e la sua precedente e porre questa più piccola della lunghezza della finestra.
e . Mi interessa sapere il numero delle risoluzioni con i vincoli sopra citati e senza vincoli.
Ed ora considero la probabilità che tutto vada bene come

Quindi è facile da calcolare. molto meno. Provo a scrivere la EGF e in effetti ho . La forma chiusa è facile da trovare: .
Qui mi blocco. Non trovo un modo furbo per esprimere la derivata n-esima da calcolare nello zero. Ci sono altre strade che riuscite a intravedere? Qualche consiglio?
Se non fosse chiaro vi prego di dirmelo e vedo di fare qualche disegnino esemplificatore.
Grazie per l'attenzione :)

[IsidoroKZ]

Hai sbagliato la domanda! Dovevi invocare direttamente PietroBaima e DirtyDeeds

[fairyvilje]

Sicuro, ma non mi piace taggare le persone .

[Sjuanez]

Tanto poi li devi pagare lo stesso, pure se passano e rispondono...

[PietroBaima]

Mi ci metto stasera a farti qualche conto, adesso la mia pausa è finita, ma al primo sguardo (ma potrei sbagliarmi, eh, mi sto lanciando) sembra che sia un problema di Saradha (Sylvester generalizzato, in pratica, dimostrato nel 2002).
Leggi qua nel caso in cui tu non lo conosca.

a stasera
Ciao
Pietro

[fairyvilje]

Mai sentito, ora guardo :)
Grazie!

[DirtyDeeds]

Prima qualche domanda di chiarimento, ché io so' tardo (tardo e basta, senza freak):

Assumo di avere una stringa di DNA di lunghezza ovvero una stringa in con .

I simboli sono equiprobabili?

Considero ora un vettore ordinato di letture, dove per ordine si intende la relazione d'ordine dei naturali tra i vari . La lunghezza di questo vettore è ovvero il numero di finestre considerate.

Le finestre possono sovrapporsi o sono disgiunte?

E intanto, posso semplificarti un po' la notazione? Mi è venuto il mal di testa Diciamo che hai finestre di larghezza , , e con indici iniziali .

Voglio ora verificare la probabilità che un certo numero di finestre scelte casualmente sia sufficiente ad evitare caratteri non coperti.

Cosa intendi per caratteri non coperti? Che nessuno tra sia in una delle finestre? O che specifiche sequenze non siano nelle finestre?

[fairyvilje]

Perdona la notazione, purtroppo ho a che fare con tantissimi simboli per ogni dimostrazione, definizione o altro ed è difficile gestirli razionalmente.

I simboli sono tutto tranne che equiprobabili . Anzi non sono nemmeno indipendenti proprio perché sono le basi dell'acido nucleico. Ma il calcolo dell'entropia è un altro problema . Teoricamente però l'alfabeto non influisce sulla "finestratura", ci pensa la metrica a tenerne conto e qui per ora non dovrebbe entrare in gioco.

Le finestre possono sovrapporsi. Anzi se non lo fanno sono dolori perché non ricostruisco un bel nulla . Quella che cerco è proprio la condizione di sovrapposizione fra almeno coppie di finestre in modo che si formi una sorta di catena.

Le finestre hanno lunghezza fissa. L'unico grado di libertà è dove iniziano nella stringa. Questo parametro è equiprobabile per ogni posizione e indipendente per le varie finestre (eccetto effetti di bordo trascurabili)

Intendo dire che la stringa ha almeno un carattere non coperto dalla finestrazione. Esempio grafico:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

5 finestre di lunghezza fissa 4.

Lo schema fidocad non gestisce bene la posizione dei quadrati in riferimento alla stringa

[DirtyDeeds]

Ok, adesso mi è più chiaro. Andiamo avanti, con qualche passo indietro:

L'unico grado di libertà è dove iniziano nella stringa. Questo parametro è equiprobabile per ogni posizione e indipendente per le varie finestre (eccetto effetti di bordo trascurabili)

Quindi ammetti che due finestre possano avere due indici iniziali uguali, cioè che si possa avere per ?

Voglio ora verificare la probabilità che un certo numero di finestre scelte casualmente sia sufficiente ad evitare caratteri non coperti.

Vorresti quindi trovare il minimo numero di finestre di larghezza necessarie per non avere buchi nella coperta?

Provo a scrivere la EGF

Cos'è EGF?

[fairyvilje]

Si confermo :).
Il numero minimo inteso non in senso deterministico, ma come probabilità che per quel numero di finestre casualmente generate il covering non abbia buchi.

È una serie formale usata per i problemi di conteggio. Viene fuori dalla combinatoria analitica. Uso le EGF e le OGF quando devo calcolare il numero di qualcosa con certi vincoli in uno spazio campionario di dimensione finita.
https://en.wikipedia.org/wiki/Generating_function#Ordinary_generating_function
https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function