ゲノコン 問題Dでやったこと
ゲノコンD問題でやったことです。途中暫定1位まで行ったのですが、そこから伸ばせませんでした。（D問題は6位）
分析用コードを消さずに提出したところを評価してもらったようで、審査員特別賞を頂くことができました。
問題の概要
- 文字A, C, G, Tからなる2本の秘密文字列sが存在する
- 2本の秘密文字列に対して観測や操作を行った結果である観測文字列が複数与えられる
- 文字列の長さは30,000〜100,000とかなり長い
- 観測文字列は、参照文字列Gとその差分を表す圧縮表現により与えられる
- 観測文字列をもとに、2本の秘密文字列を復元せよ
この問題の特徴としては、
- 通常のヒューリスティックコンテストでは、解に対応するスコアを手元で計算することが可能である。（AHC003のように不明な場合もあるが、秘密パラメータの生成方法が開示されている）
一方、今回は秘密文字列が分からないのでスコアは計算不能であり、不明なデータを推測するKaggleに近い形式の問題と言える。 - サンプルデータ数が9個と少なく、またサンプルデータと評価用のデータの性質が違うのは難しい点である。
解法
解0 - 自明解
参照文字列Gをそのまま出す → 9328点
解1 - 単純な多数決
- 観測文字列が2本あることは無視して1本だと思って、とりあえず多数決で直せばいいんじゃね？
- 挿入・削除を処理するのは面倒くさそう。不一致のみ多数決で修正する。
この方針で9790点
解法2 - 焼きなましによる観測文字列のグルーピング
問題のポイントは、それぞれの観測文字列を2つの秘密文字列のどちらかに対応するか定めることだと思いました。 粗い議論ですが、以下のように考えました。
- 観測文字列を2つの集合に分ける問題である。観測文字列の数は50-100程度と考えると、時間も十分にあるので、評価関数を定めて焼きなましで良さそう。
- ある文字にエラーが発生する確率をpとする。
観測文字列を2つに分けたとき、尤度はそれぞれの秘密文字列との差異をxとしたとき、概ねpxとなる。
尤度を最大化することを考えると、xを最小にすれば良い。 - 真の秘密文字列がわからないので、観測文字列を2つに分けたときのそれぞれの集合で、同じ位置で最大となる文字以外の総数をxとした。
これで10458点。
苦難のとき
あとは欠損・挿入を考慮してスコアを伸ばしていくだけです。まずは以下のような分析をしました。
- IGV Viewerを使って眺める
- 参照文字列, 出力解, 秘密文字列のアラインメントを合わせて出力する （これがかなり面倒くさい・・・）
そこで分かったこととしては、
- 不一致・欠損・挿入という3種類の観測エラーがあるが、不一致に関しては確かなものは直せば良い（一部は怪しい）が、2文字以上の欠損・挿入についてはかなり信用ならない。
- IGV Viewerで見て、明らかに直すべきとしか思えない欠損・挿入エラーについて、直すと不正解で減点になってしまうものがある。 全てが不正解ではなく、直すのが正解のものも20%-30%ある。長さが20とか50とかの挿入・欠損があり、正しく直せると大幅な点数増が期待できる。
各サンプルデータの満点からの差異がどこから来ているのかを把握することができた。その結果は以下である。
じゃあこれらを直せば良い点数が出る・・かというとそうではなく、これらを直そうとすると不正解になる欠損・挿入も拾ってしまう。
- 「多数決で普通に考えたら直すべき」文字列の前後を、直すと正解／不正解になるフラグを付けながら参照文字列、出力解、秘密文字列を出力したが、高い確率で正解である欠損・挿入を求める方法は分からず。
- 一点だけ有用な知見があり、挿入すべき文字列を繰り返すときは不正解である確率が高かった。これはサンプルデータでも評価データでも同じ傾向が見られた。
- タンデムリピート・イントロンなどバイオインフォマティクスのドメイン知識を得ようとしたが、スコアの改善に有用な知見は得られず。
最終提出の解法
分析の結果、解法2に加えて以下の方針を取り、10466点のものを提出しました。
- 挿入は1文字は常に採用、挿入すべき文字列を繰り返すときは不採用、そうでない場合は50文字以下を採用する
- 削除は1文字は常に採用、2文字以降の削除は不採用
