はじめに
タイトルの通りで、C言語もよくわかっていない人が何かを求めてminimap2のリポジトリをながめていきます。minimap2の使い方を調べる記事ではなくて、minimap2のリポジトリを眺める記事なので、minimap2を使いたい方にはこのページは全く参考になりません。いわゆる、個人向けの雑なメモ書きといった感じの資料です。また、アルゴリズムを知りたい人にも全く参考になりません。ごく表面的にさらっとリポジトリを眺めるだけです。
そんな残念な記事ですが、「minimap2のリポジトリを眺めてみた」みたいな記事は、日本語では皆無、もしくは皆無であることが調べずともあらかじめ予想できます。情報がないものについては、素人であっても地道に自分で調べていくしかないわけで、それでこの自分用メモの記事を公開しています。すでに情報がたくさんあるものについては、不正確であいまいな個人的なメモを追加するのは避けるべきですが、全く情報がないものについては、個人用メモのような公開であっても誰かの役に立つかも知れないので公開してもよいと考えています。
目標としては、minimap2のRubyバインディングを作成することを考えています。
追記：実際にminimap2のRubyバインディングをつくりました。
tokeiをみる
まずはRustの超便利コマンド tokei でファイルの行数を見ます。これによって大雑把なコードの規模感をつかむことができます。
===============================================================================
Language Files Lines Code Comments Blanks
===============================================================================
Autoconf 1 11 11 0 0
C 23 7060 6422 205 433
C Header 15 4030 2560 960 510
JavaScript 1 2568 2403 71 94
Makefile 2 149 109 4 36
Markdown 5 1470 0 1080 390
Perl 1 33 29 1 3
Python 2 104 90 1 13
ReStructuredText 1 196 127 0 69
Shell 1 10 7 0 3
TeX 2 1527 1277 167 83
Plain Text 1 24 0 20 4
VB6 1 930 793 0 137
===============================================================================
Total 56 18112 13828 2509 1775
===============================================================================
コードの大半C言語で、7060行、ヘッダーで4030行あるようです。これは、まあ登山でもする気持ちになれば、全部読むのは不可能ではないかもしれない量だと思います。富士山ぐらいの高さはあるかもしれません。
-
Autoconf:
- これは./configureを生成するツールだそうです。
-
Javascriptが混じっていますが、これは
paftools.jsというやつですね。なぜHeng Li氏がjavascriptで作ろうと思ったのかはわかりません。（そもそもC++ではなくCにこだわる理由もわかりませんが）paf形式というのは新しい形式みたいですね。
Paf形式
PAFは、2つのシーケンスのセット間のおおよそのマッピング位置を記述するテキストフォーマットです。PAFはTABで区切られており、各行は以下の定義済みフィールドで構成されています。
| Col | Type | Description |
|---|---|---|
| 1 | string | Query sequence name |
| 2 | int | Query sequence length |
| 3 | int | Query start (0-based; BED-like; closed) |
| 4 | int | Query end (0-based; BED-like; open) |
| 5 | char | Relative strand: "+" or "-" |
| 6 | string | Target sequence name |
| 7 | int | Target sequence length |
| 8 | int | Target start on original strand (0-based) |
| 9 | int | Target end on original strand (0-based) |
| 10 | int | Number of residue matches |
| 11 | int | Alignment block length |
| 12 | int | Mapping quality (0-255; 255 for missing) |
アライメントからPAFが生成された場合、列10は配列一致数に等しく、列11はアライメント内の配列一致、ミスマッチ、挿入および欠失の合計数に等しくなります。アライメントが利用できない場合、列１０および列１１は依然として必要であるが、非常に不正確である可能性がある。
PAFファイルは、オプションで各行の最後にSAMのようなタイプされたキーと値のペアを含んでいてもよい。
-
現時点ではPAF形式が何なのかわかりません。SAMよりも単純な形式のファイルっぽいですね。なにやらロングリード用のそういうファイルなのでしょう。
-
Pythonのコードが含まれています。これはCythonを利用して、Pythonバインディングを作成しているもののようです。Cythonは、ffiとは違って直接Pythonとやりとりするようです。私の使っているRuby言語にはCythonに相当するエコシステムが存在しないので憶測になりますが、Pythonでソースコードを書くと、それがC言語のコードに変換されて、そのレベルでバインディングを作るような仕組みのようで、速度面で優位性があるようです。
-
perlなどは、tex関連のディレクトリに含まれているようです。VB6というのが何を示しているのか不明ですが、VisualBasicのファイルがminimap2に含まれているとは思えないので、何らかの誤判定でしょう。
ディレクトリ構成を見る
さて、次にディレクトリ構成を見ていきます。
-
texはおそらくドキュメント置き場だと思います。あまり見なくても大丈夫でしょう -
testは、テストそのものではなく、テスト用のデータのみが置かれているようです。C言語のテスト文化がよくわからないのですが、ひょっとすると型ががっしりしているため、あまりテストが必要がないのかも知れません。 -
see2neonIntel CPUに対する命令を、ARM CPUに変換するツールのようです。-
ストリーミングSIMD拡張命令 - Wikipedia
- SIMDは、CPU上で並列演算やベクトル演算をする仕組みみたいです。
- SIMD - Wikipedia
- Intel AVX というやつもあるみたいですね。
- SIMDは、bwa-mem2, minialign などでもよく見るフレーズです。
- そう考えると、GPUを用いたマッパーみたいなものも将来的に出てくるのかも？
- と思ったらCUDAを使ったmethylation callerとか作ってる人が
- そう考えると、GPUを用いたマッパーみたいなものも将来的に出てくるのかも？
- see2neonは、SIMDによる並列計算のSEE命令をNEON命令に変換するやつということでしょう。
- コントリビュートしている人の流れは、ARMがほしいと言い始めたのは、オーストラリアの方。そして、別のオーストラリアの人が、プルリクエストを送って、ARMをサポートしています。また、インドの方もなんかやっています。
- まあminimapの本筋にはあまり関係ないですが、オーストラリアの研究の盛んな様子に驚きます。
-
ストリーミングSIMD拡張命令 - Wikipedia
-
PythonMappyという名前みたいですね。これはあとでしっかり見る必要があります。 -
miscpaftoolsのディレクトリです -
libここにはsimdeが入っています。ここでも出てくるSIMD はよほど重要なキーワードなのでしょう。- https://github.com/simd-everywhere/simde
- よくわかりませんが「どこでもSIMD」ということで、さまざまなCPUで動作するように移植性を改善するツールのようですね。
- 普段Rubyのスクリプトしか書いていないのでなかなか気が付きにくいですが、C言語の場合は、直接CPUに対する命令を使うので、アーキテクチャごとの差異を吸収するやつが必要になるのでしょう。
つぎに、個別のファイルを見ていきます
-
FAQ 現時点ではみてもよくわかりませんが、そういうファイルがあります。
-
ライセンスはMIT
-
Manifest.inというのがありますが、これが何かは不明です
-
MakefileとMakefile.simdeの2種類があります。 -
News というファイルがあります。HengLi氏のディレクトリを見ていて感じるのは、非常にドキュメンテーションが多くてしっかりしていることですね。これによって彼のツールは世界的な人気を獲得しているのかも知れません。
-
cookbook.md というファイルがあります。ここにはモダリティごとのベストプラクティスのようなことが書かれているようですね。
-
setup.py -
あとはC言語のソースコードのファイルのようです。
C言語のファイルの名前を見る
さて、C言語は読めませんので、大雑把にファイル名などから状況を見ていこうと思います。
真っ先に感じるのは、kalloc, ksort, kseqあれ？ これらの頭にkがつくファイル群はどこかで見たことがあるような気がするな？ですね。これらのソースコードのコメントを見ると、
Copyright (c) 2008, 2009, 2011 Attractive Chaos <attractor@live.co.uk>
とあるので、Attractive Chaos さんの作品です。つまり、htslibやbwaでも使われている有名なシリーズです。minialignでもksortは使われていますね。
klib
最新のコミットは2020年なので、現在でも多少の開発が続いているようです。
Klib は、 下で配布されるスタンドアロンの軽量Cライブラリ MIT / X11ライセンスの です。 標準Cライブラリを除いて、ほとんどのコンポーネントは外部ライブラリから独立しており、互いに独立しています。 このライブラリのコンポーネントを使用するには、ライブラリの依存関係を気にせずに、いくつかのファイルをソースコードツリーにコピーするだけで済みます。
Klibは、効率とメモリフットプリントの削減に努めています。 ハッシュテーブル、Bツリー、ベクトル、並べ替えアルゴリズムなどの一部のコンポーネントは、速度とメモリ使用量の両方の点で、すべてのプログラミング言語で同様のアルゴリズムまたはデータ構造の最も効率的な実装の1つです。
ということで見ていくと、
| ファイル名 | 説明 |
|---|---|
| khash.h | ダブルハッシュに基づく汎用ハッシュテーブル |
| kbtree.h | Bツリーに基づく一般的な検索ツリー |
| kavl.h | 一般的な侵入型AVLツリー |
| ksort.h | コムソート ：イントロソート、マージソート、ヒープソート、 、Knuthシャッフル、k-smallアルゴリズムを含む一般的なソート |
| kseq.h | 汎用ストリームバッファーとFASTA / FASTQ形式のパーサー |
| kvec.h | 汎用動的配列 |
| kdq.h | デキュー ：汎用両端キュー（ ） |
| klist.h | 一般的な単一リンクリストとメモリプール |
| kstring.h | 基本的な文字列ライブラリ |
| ketopt.h | と同様のコマンドライン引数パーサー getopt_long |
| kmath.h | 基本的な非線形計画法といくつかの特別な数学関数を含む数値ルーチン |
| kson.h | 単純な JSON パーサー（ストリーミングなし） |
| kthread.h | 単純なマルチスレッドモデル |
となっています。基本的なデータ構造とアルゴリズムのようなものをまとめたやつみたいですね。速度と性能重視のGlibみたいなやつなんでしょうかね…。Rubyの場合だと、大クラス主義の代表的存在として知られてるArrayや、Hashなどを使っていくわけですが、C言語ではそういった根源的なツールもある程度自作するか、あるいはこういう風にライブラリ？として組み込みながら使うということがわかります。これらのファイル群が、バイオ方面を超えて使われているようです。minialignではksort kvec を使っています。AttractiveChaos氏が誰かはわかりませんがHengLi氏と関係のある方でしょう。
こうやってリポジトリを眺めていて、感じるのは極度のほどのミニマリズムですね。kシリーズのライブラリすらも、まるごと利用するのではなく、必要な関数だけ切り出して使っているような印象です。速度を追求するためには、なるべくコードを削ぎ落とさなければならない。走らせることのない贅肉は決してつけてはならないと言っているようなソフトの作り方をしていると思います。
Heng Li氏自身がブログで、自作のソフトウェアのメンテナンスの方針をまとめています。
NTT未来翻訳で翻訳
これが私の個人的なプロジェクトを維持する方法です:私はそれらを維持しないようにします。目標を達成するために、
- ユーザーの質問を減らすためにユーザーインターフェースを簡素化するよう努力しています。
- プロジェクトを互いに独立させ、外部ライブラリから独立させることで、自分のプロジェクトが失敗して依存関係が変更されないようにしています。
- 既存のコード・ベースに大きな変更があったと感じた場合は、コードを複製して新しく始めることが多い(たとえば、フェルミ対フェルミ2対フェルミ-ライト、minimap対minimap 2)。
こうすることで互換性を忘れ、以前のバージョンの安定性に影響を与えることなく、技術的負債を自由に削減することができます。これらの戦略のおかげで、手に負えない混乱を残すことなく、プロジェクトを時々切り替えることができました。
こういった方針ですので、たとえklibのようなライブラリであっても、ソフトウェアの作成に本当に必要な部分だけを切り出して固定化して使っているようですね。
ksw2
kswはスミスウォーターマンのアルゴリズムに関係するやつのようです。
-
https://github.com/lh3/ksw2
Global alignment and alignment extension
READMEの最後に、こんな比較表が掲載されています。
| Library | CIGAR | Intra-seq | Affine-gap | Local | Global | Glocal | Extension |
|---|---|---|---|---|---|---|---|
| edlib | Yes | Yes | No | Very fast | Very fast | Very fast | N/A |
| KSW | Yes | Yes | Yes | Fast | Slow | N/A | Slow |
| KSW2 | Yes | Yes | Yes/dual | N/A | Fast | N/A | Fast |
| libgaba | Yes | Yes | Yes | N/A? | N/A? | N/A? | Fast |
| libssa | No | No? | Yes | Fast | Fast | N/A | N/A |
| Opal | No | No | Yes | Fast | Fast | Fast | N/A |
| Parasail | No | Yes | Yes | Fast | Fast | Fast | N/A |
| SeqAn | Yes | Yes | Yes | Slow | Slow | Slow | N/A |
| SSW | Yes | Yes | Yes | Fast | N/A | N/A | N/A |
| SWIPE | Yes | No | Yes | Fast | N/A? | N/A? | N/A |
| SWPS3 | No | Yes | Yes | Fast | N/A? | N/A | N/A |
ライバルプロダクツを徹底的に調査する姿勢がうかがえます。
さて、この記事は以上です。
README.md 終末を読むと、minimap.h にC APIが書いてあるよ、mmpriv.h により内部のAPIが書いてあるよ、ということなので、次回はこれらのソースコードを眺めることにします。