Tandem Duplications, Segmental Duplications and Deletions, and Their Applications

摘要

We review two streams of recent research results in this paper. The first is on converting a sequence A to another sequence B using the minimum number of tandem duplications. This research originates from the copying systems in computer science in the early 1980s, and also from biology more than 40 years ago. We review our recent NP-hardness result on this paper, together with several open problems along the line. Segmental duplications and deletions are more discussed recently on cancer research where besides genomes (sequences), the so-called copy number profile (a vector where the ith component represents the number of the ith segment appearing in the genome, regardless of their orders) are also used. We again review some of our recent hardness results and preliminary positive results, together with some open problems. This paper is mostly self-contained.