Open Collections

Stodgell, Curtis

The problem of motif finding plays an important role in understanding the development, function and evolution of organisms. The Planted (l, d)-Motif Problem first introduced by Pevzner and Sze [13] is a variant model of motif finding that has been widely studied. Nevertheless, despite the many different algorithms constructed to solve this problem, it is far from being solved entirely [5]. We analyze a number of algorithms including: the Basic Voting Algorithm, the Winnower and the Closest String. One thing that has become ubiquitous among these algorithms is the tradeoff between efficiency and accuracy. We formulate the motif-finding problem as a constraint satisfaction problem and introduce a special form of constraint consistency. By using a fixed-parameter algorithm for the closest string problem [4], we develop a propagation algorithm that enforces the new constraint consistency with the same worst-case time complexity as that of the standard path consistency algorithm. Experiments on randomly generated sequences indicate that our approach is effective and efficient.

Text

University of British Columbia. COSC 449

Vancouver : University of British Columbia Library

10.14288/1.0052231

Arts and Sciences, Irving K. Barber School of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/