Independent Subset of Rectangles Problem for Nonoverlapping local alignments

Question

I'd like to implement a graph-based algorithm for DNA comparison, more especially by solving a problem that can be formulated as a Maximum Weighted Independent Set problem.

I have found the article in reference [1], especially part 2.2.2 "The Independent Subset of Rectangles (IR) Problem", but it is not very explicit on the way to build the graph G given 2 DNA sequence

So I'm looking for any indication, article, or description on the way to construct the conflict graph cited in article reference [1] and [2].

I'm not from the biology world but the computer world.

Thank you very much for your help.

[1] Efficient combinatorial algorithms for DNA sequence processing: https://www.cs.uic.edu/~dasgupta/resume/publ/papers/book-chapter-dasgupta-kao.pdf

[2] Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) : https://core.ac.uk/download/pdf/82057963.pdf

Answer 1

Consider the below image from a recent review on whole genome alignment:

The lines in the figure are local alignments (sometimes referred to as anchors in literature). These lines can be maintained a number of ways, but often via pairwise genome alignment methods like LastZ, MUMmer, and Last (there are many many more).

Often times, one wants to pull out the "best set" of local alignments. In some cases, algorithms will use the "single copy" heuristic, which constrains that each nucleotide in the query can be aligned to at most one nucleotide from the reference. In this case, you can create a bounding rectangle along each of the lines, and two rectangles are independent if there is no point within either rectangle that is on the same $x$ or $y$ coordinate as any point in the other rectangle. You can use this to set your constraint graph.

However, it is worth noting that two rectangles may overlap just a tiny bit. In this case, it would be ideal to chop the overlapping part off of either rectangle, that way you can select both and not just one. This requires a bit more methodology, but a crude way would be to just look for such cases and for each one, chop the overlap off of the less scoring rectangle.