Non-overlapping Common Substrings Allowing Mutations

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

Full description

Saved in:
Bibliographic Details
Published in:Mathematics in computer science 2008-06, Vol.1 (4), p.543-555
Main Authors: Chan, H. L., Lam, T. W., Sung, W. K., Wong, P. W. H., Yiu, S. M.
Format: Article
Language:English
Subjects:
Computer Science
Mathematics
Mathematics and Statistics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:. 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.
ISSN:1661-8270
1661-8289
DOI:10.1007/s11786-007-0030-6