File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Non-overlapping common substrings allowing mutations
  • Basic View
  • Metadata View
  • XML View
TitleNon-overlapping common substrings allowing mutations
 
AuthorsChan, HL3
Lam, TW2
Sung, WK4
Wong, PWH1
Yiu, SM2
 
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
 
CitationMathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s11786-007-0030-6
 
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.
 
ISSN1661-8270
2012 SCImago Journal Rankings: 0.431
 
DOIhttp://dx.doi.org/10.1007/s11786-007-0030-6
 
DC FieldValue
dc.contributor.authorChan, HL
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSung, WK
 
dc.contributor.authorWong, PWH
 
dc.contributor.authorYiu, SM
 
dc.date.accessioned2010-09-06T09:51:57Z
 
dc.date.available2010-09-06T09:51:57Z
 
dc.date.issued2008
 
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.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.identifier.citationMathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s11786-007-0030-6
 
dc.identifier.doihttp://dx.doi.org/10.1007/s11786-007-0030-6
 
dc.identifier.epage555
 
dc.identifier.hkuros146738
 
dc.identifier.issn1661-8270
2012 SCImago Journal Rankings: 0.431
 
dc.identifier.issue4
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-58549110647
 
dc.identifier.spage543
 
dc.identifier.urihttp://hdl.handle.net/10722/89066
 
dc.identifier.volume1
 
dc.languageeng
 
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-0
 
dc.publisher.placeSwitzerland
 
dc.relation.ispartofMathematics in Computer Science
 
dc.subjectAlgorithms
 
dc.subjectConserved genes
 
dc.subjectMutations
 
dc.subjectWhole genome alignment
 
dc.titleNon-overlapping common substrings allowing mutations
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, HL</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Wong, PWH</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-09-06T09:51:57Z</date.accessioned>
<date.available>2010-09-06T09:51:57Z</date.available>
<date.issued>2008</date.issued>
<identifier.citation>Mathematics In Computer Science, 2008, v. 1 n. 4, p. 543-555</identifier.citation>
<identifier.issn>1661-8270</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/89066</identifier.uri>
<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. &#169; 2008 Springer-Verlag.</description.abstract>
<language>eng</language>
<publisher>Birkhaeuser Verlag AG. The Journal&apos;s web site is located at http://www.springer.com/dal/home/birkhauser/mathematics?SGWID=1-40292-70-173671506-0</publisher>
<relation.ispartof>Mathematics in Computer Science</relation.ispartof>
<subject>Algorithms</subject>
<subject>Conserved genes</subject>
<subject>Mutations</subject>
<subject>Whole genome alignment</subject>
<title>Non-overlapping common substrings allowing mutations</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=1661-8270&amp;volume=&amp;spage=543&amp;epage=555&amp;date=2008&amp;atitle=Non-overlapping+Common+Substrings+Allowing+Mutations+</identifier.openurl>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/s11786-007-0030-6</identifier.doi>
<identifier.scopus>eid_2-s2.0-58549110647</identifier.scopus>
<identifier.hkuros>146738</identifier.hkuros>
<identifier.volume>1</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>543</identifier.spage>
<identifier.epage>555</identifier.epage>
<publisher.place>Switzerland</publisher.place>
</item>
Author Affiliations
  1. University of Liverpool
  2. The University of Hong Kong
  3. University of Pittsburgh
  4. National University of Singapore