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