Tekniken Finite Markov Chain Imbedding (FMCI) är en klassisk metod för komplexa kombinatoriska problem relaterade till sekvenser. För att få effektiva algoritmer, är det känt att sådana metoder måste först skrivas om med rekursiva relationer. Vi föreslår här att ge här en allmän rekursiv algoritm som gör det möjligt att beräkna på ett numeriskt stabilt sätt exakt Kumulativ Distributionsfunktion (CDF) eller kompletterande CDF (CCDF). Dessa algoritmer tillämpas sedan i två särskilda fall: den lokala poängen i en sekvens och mönsterstatistik. I båda fallen är asymptotisk utveckling härledd. För den lokala värderingen möjliggör vår nya metod för första gången att beräkna exakta p-värden för en praktisk studie (att hitta hydrofobiska segment i en proteindatabas) där endast approximationer fanns tillgängliga tidigare. I denna studie verkar asymptotiska approximationer vara helt opålitliga för 99,5 % av de aktuella sekvenserna. När det gäller mönsterstatistiken överträffar de nya FMCI-algoritmerna dramatiskt de tidigare eftersom de är mer tillförlitliga, lättare att implementera, snabbare och med lägre minneskrav.
Nuel REF tillhandahåller rekursiva algoritmer för att beräkna kumulativa distributionsfunktioner (CDF) med hjälp av Finite Markov Chain Imbedding (FMCI).
Effective p-value computations using Finite Markov Chain Imbedding (FMCI): application to local score and to pattern statistics
{'venue': 'Algorithms for Molecular Biology', 'journal': 'Algorithms for Molecular Biology', 'mag_field_of_study': ['Computer Science', 'Medicine']}