Since its introduction, the double cut and join (DCJ) operation has gained popularity in Computational Biology as a convenient abstraction that generalizes various genome rearrangement operations – mutation events that affect large genome segments. The central problem involving this operation is the DCJ distance problem, which seeks to minimize the number of DCJ operations required to transform one genome into another. In particular, recent studies incorporate intergenic region sizes to obtain more realistic rearrangement distance estimates. When the genomes differ in gene content, indel (insertion or deletion) events must also be considered. We present the first algorithm for the DCJ distance that incorporates intergenic information and supports indels, a 2-approximation applicable to single-copy, co-tailed genomes.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

DCJ and Indel Distance Considering Intergenic Region Information

  • Gabriel Siqueira,
  • Alexsandro Oliveira Alexandrino,
  • Andre Rodrigues Oliveira,
  • Zanoni Dias

摘要

Since its introduction, the double cut and join (DCJ) operation has gained popularity in Computational Biology as a convenient abstraction that generalizes various genome rearrangement operations – mutation events that affect large genome segments. The central problem involving this operation is the DCJ distance problem, which seeks to minimize the number of DCJ operations required to transform one genome into another. In particular, recent studies incorporate intergenic region sizes to obtain more realistic rearrangement distance estimates. When the genomes differ in gene content, indel (insertion or deletion) events must also be considered. We present the first algorithm for the DCJ distance that incorporates intergenic information and supports indels, a 2-approximation applicable to single-copy, co-tailed genomes.