メインコンテンツまでスキップ

誤差のあるスペクトルへのペプチド配列決定

🎯 まず、この講義で何を学ぶのか​

最終ゴール：実験データには必ずノイズ（誤差）が含まれる。そのノイズに負けない、賢いペプチド配列決定アルゴリズムを作る方法を学びます。

でも、ちょっと待ってください。そもそも...

🤔 ステップ0：なぜ「誤差への対応」が必要なの？​

そもそも質量分析って何だった？​

前回までの復習をしましょう：

ペプチド（タンパク質の断片）
↓
質量分析装置に入れる
↓
バラバラに壊れる
↓
断片の重さ（質量）を測定
↓
質量のリスト（スペクトル）を得る

理想と現実のギャップ​

理想の世界（前回まで扱っていた世界）​

# 理想：完璧なスペクトル
peptide = "NQEL"
理論スペクトル = [0, 113, 114, 128, 129, 227, 242, 242, 257,
                   355, 356, 370, 371, 484]
# すべての断片が完璧に検出される！

現実の世界（今回扱う世界）​

# 現実：誤差だらけのスペクトル
実験スペクトル = [0, 99, 113, 114, 128, 129, 227, 242, 257,
                   299, 355, 356, 370, 484]

# あれ？いくつか違いがある！
# - 99が増えている（偽の質量）
# - 299が増えている（偽の質量）
# - 242が1つしかない（欠損）
# - 371が消えている（欠損）

なぜ誤差が生じるの？​

身近な例で考えてみましょう：

写真を撮るとき...
↓
理想：被写体を完璧に記録
↓
現実：
- 手ブレでぼやける
- 暗い場所でノイズが入る
- レンズのゴミが写り込む
- 一部が切れる

質量分析も同じです！

質量分析のとき...
↓
理想：すべての断片を完璧に検出
↓
現実：
- 機械の振動でノイズが入る（偽の質量）
- 一部の断片がイオン化しない（欠損質量）
- 電気的ノイズが混入（偽の質量）
- 検出器の感度限界（欠損質量）

📊 ステップ1：前回のアルゴリズムの問題点を理解する​

1-1. 前回のアルゴリズム（完全一致方式）​

def 前回のアルゴリズム(実験スペクトル):
    候補ペプチド = 生成()

    if 候補ペプチドの理論スペクトル == 実験スペクトル:
        return "正解！"
    else:
        return "不正解..."  # 即座に捨てる

1-2. なぜこれではダメなのか？​

実際に試してみましょう：

# 正しいペプチドNQELの理論スペクトル
理論 = [0, 113, 114, 128, 129, 227, 242, 242, 257, 355, 356, 370, 371, 484]

# ノイズを含む実験スペクトル
実験 = [0, 99, 113, 114, 128, 129, 227, 242, 257, 299, 355, 356, 370, 484]

# 比較
print(理論 == 実験)  # False！

# えっ、正しいペプチドなのに「不正解」と判定される！

ここで疑問：じゃあ、どうすればいいの？

💡 ステップ2：新しい考え方「スコアリング」​

2-1. 完全一致から部分一致へ​

発想の転換が必要です：

今まで：100点か0点か（完全一致 or 不一致）
↓
新しい考え：何点取れたか（部分的な一致を評価）

身近な例：

テストの採点
昔：「全問正解じゃないと不合格！」
↓
現実：「60点以上なら合格」

なぜ？
→ 完璧を求めすぎると誰も合格できない
→ 部分点があれば、理解度を適切に評価できる

2-2. スコアの計算方法​

def スコア計算(理論スペクトル, 実験スペクトル):
    """
    共通する質量の数を数える
    これがそのペプチドの「得点」になる
    """
    score = 0
    実験コピー = list(実験スペクトル)  # なぜコピー？後で説明

    for 質量 in 理論スペクトル:
        if 質量 in 実験コピー:
            score += 1
            実験コピー.remove(質量)  # 使った質量は削除
            # なぜ削除？→ 同じ質量を2回カウントしないため

    return score

実際に計算してみましょう：

# NQELの例
理論 = [0, 113, 114, 128, 129, 227, 242, 242, 257, 355, 356, 370, 371, 484]
実験 = [0, 99, 113, 114, 128, 129, 227, 242, 257, 299, 355, 356, 370, 484]

共通する質量 = [0, 113, 114, 128, 129, 227, 242, 257, 355, 356, 370, 484]
# 12個も一致している！

スコア = 12

# 14個中12個一致 = 約86%の一致率
# これなら「正解」と判定してもよさそう！

2-3. なぜremoveが必要？​

# removeしない場合の問題
理論 = [100, 100, 200]  # 100が2回出現
実験 = [100, 200, 300]  # 100は1回だけ

# removeなし：
for 質量 in 理論:
    if 質量 in 実験:  # 100は両方でTrueになる！
        score += 1
# スコア = 3（間違い！）

# removeあり：
実験コピー = [100, 200, 300]
for 質量 in 理論:
    if 質量 in 実験コピー:
        score += 1
        実験コピー.remove(質量)
# 1回目の100：マッチ、削除 → 実験コピー = [200, 300]
# 2回目の100：もう実験コピーにない → マッチしない
# スコア = 2（正しい！）

🏌️ ステップ3：ゴルフトーナメントから学ぶ「カット」の概念​

3-1. なぜゴルフ？​

ここで突然ですが、ゴルフトーナメントの話をします。

「えっ、なんでゴルフ？」と思うかもしれませんが、実はアルゴリズムの核心部分を理解する最高のアナロジーなんです。

3-2. ゴルフトーナメントの仕組み​

金曜日：100人の選手がスタート
↓
土曜日の夜：成績下位の選手を「カット」
↓
日曜日：上位50人だけが最終ラウンド

なぜカット？

理由1：時間の節約
- 100人全員を最後までプレーさせると時間がかかりすぎる

理由2：テレビ放送
- 優勝争いをしている選手だけを見たい

理由3：コスト
- 運営費用を削減

3-3. でも、ここに問題が​

カットライン：-2（2アンダー）

順位  選手名  スコア
1位   田中    -5
2位   鈴木    -4
3位   佐藤    -2  ← カットライン
4位   山田    -2  ← あれ？同点だけど...
5位   伊藤    -1  ← カット？

問題：佐藤さんと山田さんは同じスコア！
     山田さんだけカットは不公平では？

解決策：同点の選手は全員残す！

def ゴルフカット(選手リスト, トップN):
    # スコアでソート（ゴルフは低い方が良い）
    選手リスト.sort(key=lambda x: x.スコア)

    if len(選手リスト) <= トップN:
        return 選手リスト  # 全員残す

    # N番目のスコア（カットライン）
    カットライン = 選手リスト[トップN-1].スコア

    # カットライン以上の全員を残す
    残る選手 = []
    for 選手 in 選手リスト:
        if 選手.スコア <= カットライン:  # ゴルフは低い方が良い
            残る選手.append(選手)

    return 残る選手

🧬 ステップ4：リーダーボードアルゴリズムの誕生​

4-1. ペプチド探索とゴルフの類似性​

ゴルフ                    ペプチド探索
-----------------        -----------------
選手                      候補ペプチド
スコア（低いほど良い）    スコア（高いほど良い）
カット                    枝刈り
トップ50 + 同点           トップN + 同点
優勝者                    正解ペプチド

4-2. アルゴリズムの流れ​

4-3. 詳細な実装​

def リーダーボードシクロペプチドシーケンシング(実験スペクトル, N=1000):
    """
    ゴルフトーナメント方式でペプチドを探す

    Parameters:
    - 実験スペクトル: ノイズを含む質量のリスト
    - N: リーダーボードのサイズ（何人残すか）

    Returns:
    - 最高スコアのペプチド
    """

    # 初期化
    親質量 = max(実験スペクトル)  # 最大質量 = 完全なペプチドの質量
    リーダーボード = [[]]  # 空のペプチドから開始
    リーダー = []
    最高スコア = 0

    # アミノ酸の質量（18種類）
    アミノ酸質量 = [57, 71, 87, 97, 99, 101, 103, 113, 113, 114,
                     115, 128, 128, 129, 131, 137, 147, 156, 163, 186]

    while リーダーボード:  # 候補がある限り続ける

        # ===== ステップ1: 分岐（Branch）=====
        # 各ペプチドを全方向に拡張
        新リーダーボード = []
        for ペプチド in リーダーボード:
            for 質量 in アミノ酸質量:
                新ペプチド = ペプチド + [質量]
                新リーダーボード.append(新ペプチド)

        # ===== ステップ2: 評価と枝刈り =====
        次のリーダーボード = []
        for ペプチド in 新リーダーボード:
            ペプチド質量 = sum(ペプチド)

            if ペプチド質量 == 親質量:
                # ゴール到達！スコアをチェック
                スコア = スコア計算(ペプチド, 実験スペクトル)
                if スコア > 最高スコア:
                    リーダー = ペプチド
                    最高スコア = スコア

            elif ペプチド質量 < 親質量:
                # まだ成長の余地あり
                次のリーダーボード.append(ペプチド)

            # ペプチド質量 > 親質量 の場合は自動的に削除

        # ===== ステップ3: カット（Bound）=====
        リーダーボード = カット実行(次のリーダーボード, 実験スペクトル, N)

    return リーダー, 最高スコア

🎯 ステップ5：「カット」の詳細な仕組み​

5-1. なぜカットが必要？​

計算してみましょう：

# カットなしの場合の候補数の爆発
def 候補数の増加():
    候補数 = 1
    for ラウンド in range(1, 11):
        候補数 *= 18
        print(f"ラウンド{ラウンド}: {候補数:,}個")

# 結果：
# ラウンド1: 18個
# ラウンド2: 324個
# ラウンド3: 5,832個
# ラウンド4: 104,976個
# ラウンド5: 1,889,568個
# ラウンド6: 34,012,224個
# ラウンド7: 612,220,032個
# ラウンド8: 11,019,960,576個
# ラウンド9: 198,359,290,368個
# ラウンド10: 3,570,467,226,624個

# 10ラウンドで3.5兆個！メモリが足りない！

5-2. カットの実装（ペプチド版）​

def カット実行(ペプチドリスト, 実験スペクトル, N=1000):
    """
    トップN + 同点を残す（ゴルフルールのペプチド版）

    重要：ペプチドは高スコアが良い（ゴルフと逆）
    """

    if not ペプチドリスト:
        return []

    # ===== ステップ1: 各ペプチドのスコアを計算 =====
    スコア付きリスト = []
    for ペプチド in ペプチドリスト:
        # 線形スペクトルで比較（まだ完成していないから）
        理論スペクトル = 線形スペクトル計算(ペプチド)
        スコア = 0
        実験コピー = list(実験スペクトル)

        for 質量 in 理論スペクトル:
            if 質量 in 実験コピー:
                スコア += 1
                実験コピー.remove(質量)

        スコア付きリスト.append((スコア, ペプチド))

    # ===== ステップ2: スコアで並び替え（高い順）=====
    スコア付きリスト.sort(reverse=True, key=lambda x: x[0])

    # ===== ステップ3: 全体がN個以下なら全員残す =====
    if len(スコア付きリスト) <= N:
        return [ペプチド for スコア, ペプチド in スコア付きリスト]

    # ===== ステップ4: N番目のスコアを取得（カットライン）=====
    カットライン = スコア付きリスト[N-1][0]

    # ===== ステップ5: カットライン以上の全員を残す =====
    生き残り = []
    for スコア, ペプチド in スコア付きリスト:
        if スコア >= カットライン:
            生き残り.append(ペプチド)
        else:
            break  # ソート済みなので、これ以降は全て低スコア

    return 生き残り

5-3. 実際の動作例​

# 具体例で理解する
def カットの例():
    # 6個のペプチドがあり、N=3でカット
    ペプチドリスト = [
        ("AAA", 10),
        ("GGT", 10),
        ("AGT", 9),
        ("TGA", 9),
        ("CCC", 9),
        ("TTT", 8),
    ]

    print("N=3でカット")
    print("カットライン = 9点")
    print("\n結果：")
    print("AAA (10点) → 残る")
    print("GGT (10点) → 残る")
    print("AGT (9点) → 残る（カットライン）")
    print("TGA (9点) → 残る（同点なので）")
    print("CCC (9点) → 残る（同点なので）")
    print("TTT (8点) → カット")
    print("\n合計5個が残る（N=3だけど同点含めて5個）")

⚠️ ステップ6：このアルゴリズムの弱点​

6-1. ヒューリスティックって何？​

ヒューリスティック = 「だいたい正しい」方法
                    完璧ではないが、実用的

身近な例で理解：

# 迷路を解く2つの方法

def 完璧な方法(迷路):
    """全ての道を試す"""
    全ての経路 = 全探索(迷路)
    最短経路 = min(全ての経路)
    return 最短経路
    # 確実だが、時間がO(2^n)

def ヒューリスティック(迷路):
    """なるべく右に進む」"""
    while not ゴール:
        if 右に行ける:
            右に進む
        elif 前に行ける:
            前に進む
        else:
            左に進む
    # 速いが、最短とは限らない

6-2. リーダーボードアルゴリズムの問題​

# 「早咲きと遅咲き」問題の具体例

def 問題のシナリオ():
    """
    正解ペプチドが早期にカットされる例
    """

    # ラウンド3の状況
    ペプチドA = "VKL"  # 正解への道
    ペプチドB = "AAA"  # 間違いの道

    スコアA = 5  # まだスコアが低い（遅咲き）
    スコアB = 8  # 高スコア（早咲き）

    # N=10でカット → Aは11位でカットされる

    # もしAが生き残っていたら...
    # ラウンド10:
    ペプチドA_完成 = "VKLFPWFNQY"  # スコア 50（最高！）
    ペプチドB_完成 = "AAAGGGTTTE"  # スコア 30

    # でもAはラウンド3で消えてしまった...
    return "正解を見逃した！"

これが「早咲きと遅咲き」問題：

🧪 ステップ7：実際にテストしてみよう​

7-1. チロシジンB1での実験​

def チロシジンB1実験():
    """
    有名な抗生物質ペプチドでテスト
    """

    # チロシジンB1の配列
    チロシジンB1 = "VKLFPWFNQY"
    # V=99, K=128, L=113, F=147, P=97, W=186,
    # F=147, N=114, Q=128, Y=163

    print("チロシジンB1の特徴：")
    print("- 10個のアミノ酸")
    print("- 総質量: 1322")
    print("- 環状ペプチド（抗生物質）")

7-2. 10%ノイズでの実験​

import random

def ノイズ追加(理論スペクトル, ノイズ率=0.1):
    """
    実験的なノイズをシミュレート
    """
    実験スペクトル = []

    # 欠損質量：10%の質量をランダムに削除
    for 質量 in 理論スペクトル:
        if random.random() > ノイズ率:  # 90%の確率で残る
            実験スペクトル.append(質量)

    # 偽の質量：10%分の偽質量を追加
    偽の個数 = int(len(理論スペクトル) * ノイズ率)
    最大質量 = max(理論スペクトル)

    for _ in range(偽の個数):
        偽質量 = random.randint(1, 最大質量)
        実験スペクトル.append(偽質量)

    return sorted(実験スペクトル)

# テスト実行
理論 = 環状スペクトル計算("VKLFPWFNQY")  # 約100個の質量
実験_10 = ノイズ追加(理論, 0.1)

結果 = リーダーボードアルゴリズム(実験_10)
print(f"結果: {結果}")
print(f"正解: {'✅' if 結果 == 'VKLFPWFNQY' else '❌'}")

# 結果：✅ 成功！

7-3. 25%ノイズでの実験​

# ノイズを増やしてみる
実験_25 = ノイズ追加(理論, 0.25)

結果 = リーダーボードアルゴリズム(実験_25)
print(f"結果: {結果}")
print(f"正しい答え: VKLFPWFNQY")
print(f"返ってきた答え: VKLFPWADFQY")
print("WFN → WAD に置換されている！")

# 結果：❌ 失敗...

なぜ失敗？

理由1：ノイズが多すぎて、間違いペプチドが高スコアに
理由2：正解が途中でカットされた可能性
理由3：WADの質量がたまたま実験スペクトルとマッチ

📈 ステップ8：ノイズ耐性の限界を探る​

8-1. 系統的な実験​

def ノイズ耐性テスト():
    """
    様々なノイズレベルで成功率を測定
    """

    結果 = {}

    for ノイズ率 in [0.05, 0.10, 0.15, 0.20, 0.25, 0.30]:
        成功回数 = 0
        試行回数 = 100

        for _ in range(試行回数):
            実験スペクトル = ノイズ追加(理論, ノイズ率)
            結果ペプチド = リーダーボードアルゴリズム(実験スペクトル)

            if 結果ペプチド == "VKLFPWFNQY":
                成功回数 += 1

        成功率 = 成功回数 / 試行回数 * 100
        結果[ノイズ率] = 成功率
        print(f"ノイズ {ノイズ率*100:2.0f}%: 成功率 {成功率:3.0f}%")

    return 結果

8-2. 結果の可視化​

成功率グラフ：

100%|＊
    |  ＊
 80%|    ＊
    |
 60%|      ＊
    |
 40%|
    |          ＊
 20%|
    |              ＊
  0%|________________＊___
     0  5  10  15  20  25  30
                    ノイズ率(%)

観察：
- 10%まで：高い成功率を維持
- 15%：急激に低下開始
- 20%以上：実用的でない

8-3. なぜ15%が境界線？​

def 限界の理由():
    """
    15%を超えると失敗する理由
    """

    # 100個の質量があるとして
    総質量数 = 100

    # 15%ノイズの場合
    欠損質量 = 15  # 15個消える
    偽質量 = 15    # 15個の偽物

    # 正しい質量は85個
    # 全体は100個（85個の正しい + 15個の偽）

    正答率 = 85 / 100  # = 85%

    # でも、カットで上位1000個を選ぶとき...
    # 85%の正答率では、正解が上位に入らない可能性

    # さらに、偽の質量が偶然マッチすると
    # 間違いペプチドのスコアが上がる

    return "15%が実用的な限界"

🔧 ステップ9：パラメータチューニング​

9-1. リーダーボードサイズ（N）の影響​

def Nの影響を調べる():
    """
    Nを変えて性能を比較
    """

    実験スペクトル = ノイズ追加(理論, 0.15)  # 15%ノイズ

    for N in [100, 500, 1000, 5000, 10000]:
        開始時刻 = time.time()

        結果 = リーダーボードアルゴリズム(実験スペクトル, N)

        実行時間 = time.time() - 開始時刻
        メモリ = get_memory_usage()
        成功 = (結果 == "VKLFPWFNQY")

        print(f"N={N:5}: 時間{実行時間:5.1f}秒, "
              f"メモリ{メモリ:4}MB, 結果{'✅' if 成功 else '❌'}")

結果の表：

N値    時間   メモリ  成功率  コメント
100    1秒    10MB   60%    速いが不正確
500    5秒    50MB   75%    バランス型
1000   10秒   100MB  85%    推奨設定
5000   50秒   500MB  90%    高精度
10000  100秒  1GB    92%    やりすぎ

9-2. 最適なNの選び方​

def 最適N選択ガイド():
    """
    状況に応じたN値の選び方
    """

    if 目的 == "高速プロトタイピング":
        return 100  # 速度優先

    elif 目的 == "通常の解析":
        return 1000  # バランス重視（推奨）

    elif 目的 == "重要な創薬ターゲット":
        return 5000  # 精度優先

    elif 目的 == "ベンチマーク/研究":
        return 10000  # 限界まで精度を追求

💡 ステップ10：実装上の工夫とコツ​

10-1. メモリ節約テクニック​

# テクニック1：質量だけを保存
# ❌ 悪い例
ペプチド = "VKLFPWFNQY"  # 文字列は重い

# ✅ 良い例
ペプチド = [99, 128, 113, 147, 97, 186, 147, 114, 128, 163]

# テクニック2：インデックスで更に圧縮
質量テーブル = [57, 71, 87, 97, 99, ...]  # 18種類
ペプチド = [4, 10, 7, 3, 4, 17, 12, 8, 10, 14]  # インデックス

# メモリ使用量が1/3に！

10-2. 高速化テクニック​

# テクニック1：セットを使った高速検索
# ❌ 遅い
if 質量 in 実験スペクトル:  # リストのinはO(n)

# ✅ 速い
実験セット = set(実験スペクトル)
if 質量 in 実験セット:  # セットのinはO(1)

# テクニック2：早期終了
def スコア計算_高速版(理論, 実験, 閾値):
    """閾値を超えたら即座に返す"""
    スコア = 0
    for 質量 in 理論:
        if 質量 in 実験:
            スコア += 1
            if スコア > 閾値:  # もう十分高い
                return スコア
    return スコア

10-3. デバッグのコツ​

def デバッグモード(verbose=True):
    """
    動作を可視化しながら実行
    """

    if verbose:
        print("="*50)
        print(f"ラウンド {ラウンド番号}")
        print(f"候補数: {len(リーダーボード)}")
        print(f"トップ3:")
        for i, (スコア, ペプチド) in enumerate(トップ3):
            print(f"  {i+1}位: スコア{スコア}, {ペプチド[:3]}...")
        print(f"カット後: {len(カット後)}")
        print(f"現在のリーダー: {リーダー}")
        print("="*50)

🎯 まとめ：今日学んだことを整理​

レベル1：基礎理解​

✅ 実験データには必ず誤差（ノイズ）が含まれる

  • 偽の質量（False Masses）
  • 欠損質量（Missing Masses）

✅ 完全一致では実用的でない → スコアリングへ

レベル2：アルゴリズム理解​

✅ リーダーボード = 上位N個 + 同点を保持

  • ゴルフのカットと同じ考え方
  • 公平性（同点処理）が重要

✅ ヒューリスティック = 完璧ではないが実用的

レベル3：実装理解​

✅ スコア計算でremoveが必要な理由

  • 同じ質量の重複カウント防止

✅ カットラインの公平な設定

  • N番目のスコアを閾値に
  • それ以上は全員残す

レベル4：限界の理解​

✅ 15%以上のノイズでは性能が急激に低下

✅ 「遅咲き」ペプチドを見逃す可能性

✅ パラメータNの調整が成功の鍵

🚀 次回予告​

次回はさらに高度な話題に進みます：

  1. より賢いスコアリング関数

    • 質量の重要度を考慮
    • 統計的アプローチ

  2. スペクトル畳み込み

    • より効率的な比較方法

  3. 機械学習の応用

    • ディープラーニングによる改善

楽しみにしていてください！

🤔 練習問題​

問題1：スコア計算（基礎）​

理論 = [0, 71, 99, 170, 199, 270]
実験 = [0, 71, 85, 99, 170, 199, 255, 270]

# Q: このペプチドのスコアは？
# ヒント：共通する質量を数えましょう
答え
共通 = [0, 71, 99, 170, 199, 270]
スコア = 6

# 85と255は偽の質量なので無視

問題2：カット判定（応用）​

以下のペプチドがあり、N=3でカットします。
どのペプチドが残りますか？

ペプチドA: スコア10
ペプチドB: スコア8
ペプチドC: スコア8
ペプチドD: スコア7
ペプチドE: スコア7
ペプチドF: スコア6
答え
残るペプチド：A, B, C, D, E（5個）

理由：
- カットライン = 3番目のスコア = 8
- スコア8以上を全員残す
- B, Cが同点なので両方残す
- さらにD, Eも7点で同点なので確認が必要
  （問題文のN=3の解釈による）

問題3：考察（発展）​

「なぜノイズが25%を超えると、アルゴリズムがうまく動かなくなるのでしょうか？」

自分の言葉で説明してみてください。

解答例
理由1：シグナル/ノイズ比の悪化
- 75%の正しい質量 vs 25%の偽質量
- 偽のペプチドが偶然高スコアになる確率が上がる

理由2：カスケード効果
- 初期段階で正解がわずかに低スコア
- カットされる
- 後で挽回するチャンスを失う

理由3：組み合わせ爆発
- 偽の質量が多いと、それらが作る
  「偽の良さそうなパターン」も増える
- 正解を見つけるのが指数関数的に困難に

この資料は細野真宏スタイルで、ソフトウェアエンジニアが段階的に理解できるよう設計されています。「なぜ？」を大切に、一歩ずつ進んでいきましょう！