# Independent Subset of Rectangles Problem for Nonoverlapping local alignments

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 , 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  and .

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

Thank you very much for your help.

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

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

Consider the below image from a recent review on whole genome alignment: 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.