**Conference Paper:**Non-overlapping common substrings allowing mutations

Title | Non-overlapping common substrings allowing mutations |
---|---|

Authors | Chan, HL3 Lam, TW2 Sung, WK4 Wong, PWH1 Yiu, SM2 |

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?] DOI: http://dx.doi.org/10.1007/s11786-007-0030-6 |

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. |

ISSN | 1661-8270 |

DOI | http://dx.doi.org/10.1007/s11786-007-0030-6 |

DC Field | Value |
---|---|

dc.contributor.author | Chan, HL |

dc.contributor.author | Lam, TW |

dc.contributor.author | Sung, WK |

dc.contributor.author | Wong, PWH |

dc.contributor.author | Yiu, SM |

dc.date.accessioned | 2010-09-06T09:51:57Z |

dc.date.available | 2010-09-06T09:51:57Z |

dc.date.issued | 2008 |

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. |

dc.description.nature | link_to_subscribed_fulltext |

dc.identifier.citation | Mathematics 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.doi | http://dx.doi.org/10.1007/s11786-007-0030-6 |

dc.identifier.epage | 555 |

dc.identifier.hkuros | 146738 |

dc.identifier.issn | 1661-8270 |

dc.identifier.issue | 4 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-58549110647 |

dc.identifier.spage | 543 |

dc.identifier.uri | http://hdl.handle.net/10722/89066 |

dc.identifier.volume | 1 |

dc.language | eng |

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 |

dc.publisher.place | Switzerland |

dc.relation.ispartof | Mathematics in Computer Science |

dc.subject | Algorithms |

dc.subject | Conserved genes |

dc.subject | Mutations |

dc.subject | Whole genome alignment |

dc.title | Non-overlapping common substrings allowing mutations |

dc.type | Conference_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. © 2008 Springer-Verlag.</description.abstract> <language>eng</language> <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</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&issn=1661-8270&volume=&spage=543&epage=555&date=2008&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

- University of Liverpool
- The University of Hong Kong
- University of Pittsburgh
- National University of Singapore