パセリなずな

[Yuichi Shiraishi @friend1_ws]

New from the lab by algorithm geek @ocxtal: hashing by intervals of k-mers dramatically improves genome assembly in highly repetitive regions like centromeres.

[パセリなずな @ocxtal]

そういえばこれはMRを打って、家のマシンはRyzen 9 7950Xになったのでした

[パセリなずな @ocxtal]

マシンを新しくするのは次なにかワクチンを打ってからにしよう。こないだ検査したらはしかの抗体価がちょっと低かったので打っておくか

[パセリなずな @ocxtal]

@gggtta わいわい (アルゴリズム考えるのひさびさになかなか楽しいです)

[パセリなずな @ocxtal]

Our preprint is out! A small tweak in seeding greatly improves the assembly of centromeric repeats. https://t.co/tHrHrovKAE

[パセリなずな @ocxtal]

しばらくbioinformaticsから離れていましたが、新たに機会をいただいてここ1年ほど取り組んでいた内容です。ちょっと面白いアルゴリズムになってよかった。ultra-long readのアセンブラであれば入れておいて損はないアルゴリズムなはずと思っており、広く使われるようになるといいなと思っています

[パセリなずな @ocxtal]

実装はこちら https://t.co/4IerwafQtl

[パセリなずな @ocxtal]

@miil117 元気だよ!

[パセリなずな @ocxtal]

@a4lg 差分表現 (bit並列表現) を使わず、元の定義通りのDP変数をu8で保持して斜めスライスのSIMD並列に落とす (縦横方向の依存をcarry chainにmapできない代わりに、scoreベクタをu8比較命令を使ってon-the-flyで計算する) 実装の方がトータルで速い可能性などが考えられます

[パセリなずな @ocxtal]

@a4lg この実装は差分変数列をaccumulateする部分のコストがとても大きいので、必ずしもbit並列でやるのが最速となるわけではないかもしれません。たとえば入力配列の片方の長さが255以下という制約を付加してよければ、

[パセリなずな @ocxtal]

@a4lg もちろん「dLCSの値を陽に保持する必要がない」以外にもlLCSに帰着できない暗黙の制約が存在する場合はいろいろあると思います。ただ暗黙の制約の全貌を把握していない範囲での私の直感では、今回の例はHyyrö (2017) の結果をそのまま適用できるケースに該当しそうに思います

[パセリなずな @ocxtal]

@a4lg つまり、おそらく今回書かれたRustコードも、適切な変数変換を介せば https://t.co/FCMX6Tt9xQ で挙げたような既存のlLCSのbit並列アルゴリズムの変種らと同値なのでは、ということです

[パセリなずな @ocxtal]

@a4lg その理解でよければ、LCSでも同様のことが行われていて、Heikki Hyyro氏がoperation数の少ないアルゴリズムを提案されています。その系譜のSOTAは Hyyro (2017) "Mining Bit-Parallel LCS-length Algorithms" のようです

[パセリなずな @ocxtal]

@a4lg 私が一連のスレッド内で書いたLCS-distance (dLCS)、LCS-length (lLCS)、および一般化LCSは、すべてmatchが連続する要求を課さない方の定式化、longest common subsequenceを指しています (混同しやすいのを明記しておらずすみません :bow:)

[パセリなずな @ocxtal]

@a4lg あれ、このdiff https://t.co/FMBiRzN6Ty を見る限り、ここで使っている定式化は、matchが連続する要求を課さない方、つまり一般にlongest common subsequenceと呼ばれる方かと思っているのですが、違いましたか...?

[パセリなずな @ocxtal]

@a4lg ここまでの話は「一般化LCSは縦横斜め差分が2値となる。この性質を応用し、一般化LCSは64個の縦横差分をそれぞれ1つの64bitレジスタで保持するbit並列アルゴリズムに帰着できる。bit並列の具体的な形は1つではなく、Hyyrö氏らの変種のほかに、今回新しい変種を発見した」という理解になりそうです

[パセリなずな @ocxtal]

@a4lg 文字ペアにスコアを与える関数が2値 (たとえば f(x,y) := x == y ? eq_award : -neq_penalty) で、neq_penalty = 2*gap_penltyの場合、適当な変数変換 (と必要に応じて符号反転) でdLCSもしくはlLCSのDPに帰着します。このdLCSやlLCSと同値な文字列比較基準を、仮に一般化LCSと呼んでみます