Please use this identifier to cite or link to this item:
Title: Non-overlapping common substrings allowing mutations
Authors: Chan, H.L.
Lam, T.W.
Sung, W.K. 
Wong, P.W.H.
Yiu, S.M.
Keywords: Algorithms
Conserved genes
Whole genome alignment
Issue Date: 2008
Citation: Chan, H.L., Lam, T.W., Sung, W.K., Wong, P.W.H., Yiu, S.M. (2008). Non-overlapping common substrings allowing mutations. Mathematics in Computer Science 1 (4) : 543-555. ScholarBank@NUS Repository.
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.
Source Title: Mathematics in Computer Science
ISSN: 16618270
DOI: 10.1007/s11786-007-0030-6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Jun 11, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.