File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/BIBE.2005.12
- Scopus: eid_2-s2.0-33751167615
Conference Paper: An efficient algorithm for the extended (l,d)-motif problem with unknown number of binding sites
Title | An efficient algorithm for the extended (l,d)-motif problem with unknown number of binding sites |
---|---|
Authors | |
Issue Date | 2005 |
Publisher | IEEE, Computer Society. |
Citation | Proceedings - Bibe 2005: 5Th Ieee Symposium On Bioinformatics And Bioengineering, 2005, v. 2005, p. 11-18 How to Cite? |
Abstract | 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, Styczynsfd 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. © 2005 IEEE. |
Persistent Identifier | http://hdl.handle.net/10722/45554 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Leung, HCM | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.date.accessioned | 2007-10-30T06:29:03Z | - |
dc.date.available | 2007-10-30T06:29:03Z | - |
dc.date.issued | 2005 | en_HK |
dc.identifier.citation | Proceedings - Bibe 2005: 5Th Ieee Symposium On Bioinformatics And Bioengineering, 2005, v. 2005, p. 11-18 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/45554 | - |
dc.description.abstract | 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, Styczynsfd 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. © 2005 IEEE. | en_HK |
dc.format.extent | 172013 bytes | - |
dc.format.extent | 5052 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
dc.language | eng | en_HK |
dc.publisher | IEEE, Computer Society. | en_HK |
dc.relation.ispartof | Proceedings - BIBE 2005: 5th IEEE Symposium on Bioinformatics and Bioengineering | en_HK |
dc.rights | ©2005 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. | - |
dc.title | An efficient algorithm for the extended (l,d)-motif problem with unknown number of binding sites | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Leung, HCM:cmleung2@cs.hku.hk | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Leung, HCM=rp00144 | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/BIBE.2005.12 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33751167615 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33751167615&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2005 | en_HK |
dc.identifier.spage | 11 | en_HK |
dc.identifier.epage | 18 | en_HK |
dc.identifier.scopusauthorid | Leung, HCM=35233742700 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.citeulike | 4313183 | - |