Access Restriction

Author Leung, Henry C. M. ♦ Chin, Francis Y. L.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Little Sense ♦ Main Contribution ♦ Fast Solution ♦ Molecular Biology ♦ Efficient Algorithm ♦ Dna Sequence ♦ Length-14 Motif ♦ Common Pattern ♦ Motif Problem ♦ Motif-discovering Algorithm Software ♦ Important Problem ♦ Input Parameter ♦ Motif Length ♦ Redefined Problem ♦ Realistic Robust Result ♦ Unknown Number ♦ Minimum Number ♦ Long Time
Description Finding common patterns, or motifs, from a set of DNA sequences is an important problem in molecular biology. Most motif-discovering algorithms/software require the length of the motif as input. Motivated by the fact that the motif’s length is usually unknown in practice, Styczynski et al. introduced the Extended (l,d)-Motif Problem (EMP), where the motif’s length is not an input parameter. Unfortunately, the algorithm given by Styczynski et al. to solve EMP can take an unacceptably long time to run, e.g. over 3 months to discover a length-14 motif. This paper makes two main contributions. First, we eliminate another input parameter from EMP: the minimum number of binding sites in the DNA sequences. Fewer input parameters not only reduces the burden of the user, but also may give more realistic/robust results since restrictions on length or on the number of binding sites make little sense when the best motif may not be the longest nor have the largest number of binding sites. Second, we develop an efficient algorithm to solve our redefined problem. The algorithm is also a fast solution for EMP (without any sacrifice to accuracy) making EMP practical. 1.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01
Publisher Institution In Proceedings of the Fifth IEEE Symposium on Bioinformatics and Bioengineering (BIBE’05