Heuristics Based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions

2025 · doi:10.32388/nci96c
preprint OA: closed
Full text JSON View at publisher

Abstract

In this work, we explore heuristics for the Adjacency Graph Packing problem, which can be applied to the Double Cut and Join (DCJ) Distance Problem. The DCJ is a rearrangement operation and the distance problem considering it is a well established method for genome comparison. Our heuristics will use the structure called adjacency graph adapted to include information about intergenic regions, multiple copies of genes in the genomes, and multiple circular or linear chromosomes. The only required property from the genomes is that it must be possible to turn one into the other with DCJ operations. We propose one greedy heuristic and one heuristic based on Genetic Algorithms. Our experimental tests in artificial genomes show that the use of heuristics is capable of finding good results that are superior to a simpler random strategy.
Full text 621 characters · extracted from oa-doi-fallback · click to expand
There is a newer version available for this {{ publicationType }}. View latest version {{ publication.field_name }} {{ publication.subfield_name }} Copyright: © {{ publicationYear }} {{ publication.presentation_authors[0].full_name + (publication.presentation_authors.length > 1 ? ' et al' : '') }}. This is an open access publication distributed under the terms of the CC BY 4.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Check the {{ publicationType | capitalize }} Source for copyright and license information. Listen on

Text is read by the "Ask this paper" AI Q&A widget below. Extraction quality varies by source — PMC NXML preserves structure cleanly, OA-HTML may include some navigation residue, and OA-PDF can have broken hyphenation. The publisher copy (via DOI) is the canonical version.

My notes (saved in your browser only)

⚙ Ask this paper AI returns verbatim quotes from the full text · source: oa-doi-fallback ⓘ

Answers must be backed by verbatim quotes from this paper's full text. Hallucinated quotes are dropped automatically; if no verbatim passage answers the question, we say so. How this works

Citation neighborhood (no data yet)

We don't have any in-corpus citations linked to this paper yet. This is a recent paper (2025) — citers typically take a year or two to land, and the OpenAlex reference graph may still be filling in.

Source provenance

europepmc
last seen: 2026-05-20T01:45:00.602351+00:00