Can I read Methods for Reconstructing the History of Tandem Repeats and Their Application to the Human Genome on EtoBox?

Methods for Reconstructing the History of Tandem Repeats and Their Application to the Human Genome by Deep Jaitly; Paul Kearney; Guohui Lin; Bin Ma is a Computer Science article available to read on EtoBox.

What is Methods for Reconstructing the History of Tandem Repeats and Their Application to the Human Genome about?

The genomes of many species are dominated by short sequences repeated consecutively called tandem repeats. An understanding of the biological mechanisms that create and extend tandem repeats would be facilitated by reconstructing the history of duplication events that generated the tandem repeats. This paper explores the computational problem of reconstructing the duplication history of a tandem repeat. Specifically, the problem of reconstructing the minimum-cost duplication history is proved to be NP-hard even if the lengths and boundaries for the duplication events are fixed. When the lengths and boundaries are fixed, the minimum-cost duplication history can actually be represented by a tree. A nontrivial extension of the tree-alignment algorithms from [Wang et al. (Algorithmica 16 (1996) 302; SIAM J. Comput. 30 (1) (2000) 283)] gives a polynomial time approximation scheme (PTAS) for this special case. Experiments on more than 9000 tandem repeats from human chromosomes 1 and 22 demonstrate that our PTAS generates less costly histories in acceptable time than other heuristic methods. We also note that our PTAS works for any metric space. Therefore, our algorithm is also a PTAS for

Who reads Methods for Reconstructing the History of Tandem Repeats and Their Application to the Human Genome?

Author

Deep Jaitly; Paul Kearney; Guohui Lin; Bin Ma

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)