File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Non-overlapping common substrings allowing mutations

TitleNon-overlapping common substrings allowing mutations
Authors
KeywordsAlgorithms
Conserved genes
Mutations
Whole genome alignment
Issue Date2008
PublisherBirkhaeuser 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?
AbstractThis 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 Identifierhttp://hdl.handle.net/10722/89066
ISSN
2015 SCImago Journal Rankings: 0.337

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorWong, PWHen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-06T09:51:57Z-
dc.date.available2010-09-06T09:51:57Z-
dc.date.issued2008en_HK
dc.identifier.citationMathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555en_HK
dc.identifier.issn1661-8270en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89066-
dc.description.abstractThis 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.languageengen_HK
dc.publisherBirkhaeuser Verlag AG. The Journal's web site is located at http://www.springer.com/dal/home/birkhauser/mathematics?SGWID=1-40292-70-173671506-0en_HK
dc.relation.ispartofMathematics in Computer Scienceen_HK
dc.subjectAlgorithmsen_HK
dc.subjectConserved genesen_HK
dc.subjectMutationsen_HK
dc.subjectWhole genome alignmenten_HK
dc.titleNon-overlapping common substrings allowing mutationsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s11786-007-0030-6en_HK
dc.identifier.scopuseid_2-s2.0-58549110647en_HK
dc.identifier.hkuros146738en_HK
dc.identifier.volume1en_HK
dc.identifier.issue4en_HK
dc.identifier.spage543en_HK
dc.identifier.epage555en_HK
dc.publisher.placeSwitzerlanden_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats