Pythonではじめるバイオインフォマティクス ―可読性・拡張性・再現性のあるコードを書くために

10章

最長共通部分配列の探索：k-merの探索、関数の記述、バイナリサーチの利用

　Rosalind LCSMチャレンジ（https://oreil.ly/SONgC）でも記述されているように、ここでの演習の目的は、与えられたFASTAファイルにあるすべての配列から最長の共通部分配列を見つけることです。第8章では、複数の配列の中から対象となる配列を探しました。今回の課題では、共通部分配列が存在するのかどうかもわかりませんし、存在したとしても長さや構成がわからない状況からのチャレンジになります。そのためすべての配列に対し、任意の長さで共通部分配列を探す必要があります。この課題は、これまでの章で紹介した多くのアイデアを組み合わせなければ解けない難しい問題です。様々な手法を用い、アルゴリズムの設計、関数、テスト、コードの構成を探っていきましょう。

　この章では以下のことを学びます。

• k-merを用い共通部分配列を見つける方法
• itertools.chain()を用いてリストを要素とするリストと連結する方法
• バイナリサーチを使う方法とその理由
• 関数を最大限有活用する1つの方法
• min()とmax()でkeyオプションを使用する方法

10.1　はじめましょう

　この課題のコードとテストは、すべて10_lcsmディレクトリにあります。最初の解法をlcsm.pyプログラムにコピーして、helpを呼び出してみましょう。

$ cp solution1_kmers_imperative.py lcsm.py$ ./lcsm.py -husage: lcsm.py [-h] FILELongest Common Substringpositional arguments: FILE Input ...