Att upptäcka ungefär upprepade mönster, eller motiv, i biologiska sekvenser är ett viktigt och omfattande problem i beräkningsmolekylär biologi. Oftast uppstår motivsökningstillämpningar när man identifierar delade regulatoriska signaler inom DNA-sekvenser eller delade funktionella och strukturella element inom proteinsekvenser. På grund av mångfalden av sammanhang där motivfynd tillämpas studeras ofta flera varianter av problemet. Vi introducerar en mångsidig combinatorial optimering ram för motivfynd att par graf beskärning tekniker med ett nytt heltal linjär programmering formulering. Vår strategi är flexibel och robust nog att modellera flera varianter av motivfyndighetsproblem, bland annat de som innehåller substitutionsmatriser och fylogenetiska avstånd. Dessutom ger vi en strategi för att bestämma statistisk betydelse av avtäckta motiv. Vid testning av ett stort antal DNA- och proteindata visar vi att vårt tillvägagångssätt vanligtvis identifierar statistiskt signifikanta motiv som motsvarar antingen kända motiv eller andra motiv med hög bevarandegrad. Dessutom, i de flesta fall, finner vårt tillvägagångssätt bevisligen optimala lösningar på det underliggande optimeringsproblemet. Våra resultat visar att en kombinerad grafteoretisk och matematisk programmering kan ligga till grund för effektiva och kraftfulla tekniker för olika motivsökningstillämpningar.
Ett heltal linjär programmering (ILP) formulering av problemet presenterades också i REF.
A combinatorial optimization approach for diverse motif finding applications
{'venue': 'Algorithms for Molecular Biology', 'journal': 'Algorithms for Molecular Biology', 'mag_field_of_study': ['Medicine', 'Computer Science']}