File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s11786-007-0030-6
- Scopus: eid_2-s2.0-58549110647
- WOS: WOS:000213958600002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Non-overlapping common substrings allowing mutations
Title | Non-overlapping common substrings allowing mutations |
---|---|
Authors | |
Keywords | Algorithms Conserved genes Mutations Whole genome alignment |
Issue Date | 2008 |
Publisher | Birkhaeuser Verlag AG. The Journal's web site is located at http://www.springer.com/dal/home/birkhauser/mathematics?SGWID=1-40292-70-173671506-0 |
Citation | Mathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555 How to Cite? |
Abstract | This paper studies several combinatorial problems arising from finding the conserved genes of two genomes (i.e., the entire DNA of two species). The input is a collection of n maximal common substrings of the two genomes. The problem is to find, based on different criteria, a subset of such common substrings with maximum total length. The most basic criterion requires that the common substrings selected have the same ordering in the two genomes and they do not overlap among themselves in either genome. To capture mutations (transpositions and reversals) between the genomes, we do not insist the substrings selected to have the same ordering. Conceptually, we allow one ordering to go through some mutations to become the other ordering. If arbitrary mutations are allowed, the problem of finding a maximum-length, non-overlapping subset of substrings is found to be NP-hard. However, arbitrary mutations probably overmodel the problem and are likely to find more noise than conserved genes. We consider two criteria that attempt to model sparse and non-overlapping mutations. We show that both can be solved in polynomial time using dynamic programming. © 2008 Springer-Verlag. |
Persistent Identifier | http://hdl.handle.net/10722/89066 |
ISSN | 2023 Impact Factor: 1.1 2023 SCImago Journal Rankings: 0.265 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Sung, WK | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.contributor.author | Yiu, SM | en_HK |
dc.date.accessioned | 2010-09-06T09:51:57Z | - |
dc.date.available | 2010-09-06T09:51:57Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Mathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555 | en_HK |
dc.identifier.issn | 1661-8270 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89066 | - |
dc.description.abstract | This paper studies several combinatorial problems arising from finding the conserved genes of two genomes (i.e., the entire DNA of two species). The input is a collection of n maximal common substrings of the two genomes. The problem is to find, based on different criteria, a subset of such common substrings with maximum total length. The most basic criterion requires that the common substrings selected have the same ordering in the two genomes and they do not overlap among themselves in either genome. To capture mutations (transpositions and reversals) between the genomes, we do not insist the substrings selected to have the same ordering. Conceptually, we allow one ordering to go through some mutations to become the other ordering. If arbitrary mutations are allowed, the problem of finding a maximum-length, non-overlapping subset of substrings is found to be NP-hard. However, arbitrary mutations probably overmodel the problem and are likely to find more noise than conserved genes. We consider two criteria that attempt to model sparse and non-overlapping mutations. We show that both can be solved in polynomial time using dynamic programming. © 2008 Springer-Verlag. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Birkhaeuser Verlag AG. The Journal's web site is located at http://www.springer.com/dal/home/birkhauser/mathematics?SGWID=1-40292-70-173671506-0 | en_HK |
dc.relation.ispartof | Mathematics in Computer Science | en_HK |
dc.subject | Algorithms | en_HK |
dc.subject | Conserved genes | en_HK |
dc.subject | Mutations | en_HK |
dc.subject | Whole genome alignment | en_HK |
dc.title | Non-overlapping common substrings allowing mutations | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1661-8270&volume=&spage=543&epage=555&date=2008&atitle=Non-overlapping+Common+Substrings+Allowing+Mutations+ | en_HK |
dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Yiu, SM=rp00207 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s11786-007-0030-6 | en_HK |
dc.identifier.scopus | eid_2-s2.0-58549110647 | en_HK |
dc.identifier.hkuros | 146738 | en_HK |
dc.identifier.volume | 1 | en_HK |
dc.identifier.issue | 4 | en_HK |
dc.identifier.spage | 543 | en_HK |
dc.identifier.epage | 555 | en_HK |
dc.identifier.isi | WOS:000213958600002 | - |
dc.publisher.place | Switzerland | en_HK |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Sung, WK=13310059700 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_HK |
dc.identifier.issnl | 1661-8270 | - |