TransWikia.com

Help understanding a theorem Kleinberg proves related to sequence alignment

Computer Science Asked by mooglin on October 21, 2021

This is from Kleinberg’s Algorithm Design text (Theorem 6.14)

Let $M$ be an alignment of $X$ and $Y$. If $(m, n) notin M$, then either the $m^{text{th}}$ position of $X$ or the $n^{text{th}}$ position of $Y$ is not matched in $Y$.

The theorem does not state that $m, n$ must be the last elements of $X$ and $Y$ respectively, but earlier, when introducing the topic, he uses $m, n$ to denote the last entries of the two strings. Which of these is correct?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP