<p>Consider the below image from <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6450745/" rel="nofollow noreferrer">a recent review on whole genome alignment</a>:
<a href="https://i.sstatic.net/XroLC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XroLC.png" alt="enter image description here" /></a></p>
<p>The lines in the figure are local alignments (sometimes referred to as <em>anchors</em> 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).</p>
<p>Often times, one wants to pull out the &quot;best set&quot; of local alignments. In some cases, algorithms will use the &quot;single copy&quot; 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 <span class="math-container">$x$</span> or <span class="math-container">$y$</span> coordinate as any point in the other rectangle. You can use this to set your constraint graph.</p>
<p>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.</p>

CC BY-SA 4.0
2022-01-07T15:47:16.347Z
2022-01-07T15:47:16.347Z
Throckmorton
<p>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.</p>
<p>I have found the article in reference [1], especially part 2.2.2 &quot;The Independent Subset of Rectangles (IR) Problem&quot;, but it is not very explicit on the way to build the graph G given 2 DNA sequence</p>
<p>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].</p>
<p>I'm not from the biology world but the computer world.</p>
<p>Thank you very much for your help.</p>
<p>[1] Efficient combinatorial algorithms
for DNA sequence processing: <a href="https://www.cs.uic.edu/%7Edasgupta/resume/publ/papers/book-chapter-dasgupta-kao.pdf" rel="nofollow noreferrer">https://www.cs.uic.edu/~dasgupta/resume/publ/papers/book-chapter-dasgupta-kao.pdf</a></p>
<p>[2] Nonoverlapping local alignments (weighted independent
sets of axis-parallel rectangles) : <a href="https://core.ac.uk/download/pdf/82057963.pdf" rel="nofollow noreferrer">https://core.ac.uk/download/pdf/82057963.pdf</a></p>

<phylogenetics>
Independent Subset of Rectangles Problem for Nonoverlapping local alignments
# Independent Subset of Rectangles Problem for Nonoverlapping local alignments

(Asked by: username_0 on 2022-01-07)

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](https://www.cs.uic.edu/%7Edasgupta/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>

**Tags:** phylogenetics

---

## 1 answers

### Answer by username_1 on 2022-01-07. Score: 1

Consider the below image from [a recent review on whole genome alignment](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6450745/):
[![enter image description here](https://i.sstatic.net/XroLC.png)](https://i.sstatic.net/XroLC.png)

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.


---

