Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s11786-007-0030-6 | Mathematics in Computer Science |
Keywords | Field | DocType |
mutations,. whole genome alignment,conserved genes,algorithms.,polynomial time,algorithms | Genome,Discrete mathematics,Dynamic programming,Combinatorics,Substring,Gene,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
1 | 4 | 1661-8270 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ho-Leung Chan | 1 | 471 | 25.23 |
| Tak-Wah Lam | 2 | 1860 | 164.96 |
| Wing-Kin Sung | 3 | 1379 | 128.24 |
| Prudence W. H. Wong | 4 | 374 | 38.69 |
| S. M. Yiu | 5 | 528 | 44.78 |