ABSTRACT Problemet med upptäckt av motiv består i att hitta överrepresenterade mönster i en samling biosekvenser. Det är ett av de klassiska sekvensanalysproblemen, men har fortfarande inte lösts på ett tillfredsställande sätt på ett exakt och effektivt sätt. Detta beror delvis på det stora antalet möjligheter att definiera motivets sökyta och begreppet överrepresentation. Även för väl definierade formaliseringar löses problemet ofta på ett ad hoc-sätt med heuristik som inte garanterar att hitta det bästa motivet. Resultat: Vi visar hur man löser motivet upptäckt problem (nästan) exakt på ett praktiskt relevant utrymme av IUPAC generaliserade sträng mönster, med hjälp av p-värdet med avseende på en i.i.d. Modell eller Markovmodell som mått på överrepresentation. I synnerhet (i) använder vi en mycket exakt sammansättning Poisson approximation för nollfördelning av antalet motiv förekomster. Vi visar hur man beräknar den exakta klumpstorleksfördelning med hjälp av en nyligen införd enhet som kallas probabilistic aritmetic automaton (PAA). ii) Vi definierar två p-värdespoäng för överrepresentation, det första baserat på det totala antalet motivhändelser, det andra baserat på antalet sekvenser i en samling med minst en förekomst. (iii) Vi beskriver en algoritm för att upptäcka det optimala mönstret med avseende på någon av poängen. Metoden utnyttjar monotonicitetsegenskaper hos sammansättningen Poisson approximation och är genom storleksordningar snabbare än uttömmande uppräkning av IUPAC strängar (11,8 h jämfört med en extrapolerad körtid på 4,8 år). (iv) Vi motiverar användningen av de föreslagna poängen för motivfyndighet genom att visa vår metod för att överträffa andra motivfyndighetsalgoritmer (t.ex. MEME, Weeder) om referensdatauppsättningar. Vi föreslår också nya motiv på Mycobacterium tuberculos. Tillgänglighet och genomförande: Metoden har implementerats i Java. Det kan erhållas från
Marschall och Rahmann REF föreslår en metod för att beräkna p-värden med avseende på oberoende och identiskt fördelade (i.i.d.) och Markov modeller.
Efficient exact motif discovery
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}