KM-55｜情報Ⅰ 対策問題
令和8年度追・再試験 第1問 問2 ゲノムとは生物が持つすべての遺伝情報のことであり、A・T・G・Cの4種類の文字の列で表現される。ヒトゲノム(人間のゲノム)はおよそ30億もの長さの文字列となり、その文字列中には同じパターンが何度も出現する。何度も出現するパターンに記号を割り当てる処理を繰り返し行うことで、文字列を簡潔に表現できる場合がある。 図の文字列(4)に対して、GTTというパターンに記号α、ATTというパターンに記号βを割り当てる。さらにβαというパターンに記号γを割り当てれば、(4)は図の(5)のように表現できる。空欄「ウ」に入れるのに最も適当なものを選べ。
解答・解説を見る
正解: 1
正答
1
問題の整理
長い文字列の中の「よく出るパターン」に短い記号を割り当てて全体を短くする——これはデータ圧縮の基本的な考え方(置き換えによる圧縮)です。この問題では2段階の置き換えを正確に実行できるかが問われています。
解き方
まず GTT→α、ATT→β で置き換えます。元の文字列を3文字ずつ区切ると
GTT GTT GTT ATT GTT ATT GTT ATT GTT
→ α α α β α β α β α次に「βα」→γ で置き換えます。α α α β α β α β α の後半に「βα」が3回連続で現れるので、
α α α (βα)(βα)(βα) → α α α γ γ γ
よって「αααγγγ」となります。区切る位置を間違えないよう、必ず左から順に3文字ずつ区切ってから置き換えるのがコツです。
ちなみに、同じ文字列でも、どのパターンに記号γを割り当てるかによって圧縮後の表現は変わります(次の問題で実際に確かめます)。どのパターンを選ぶかで結果が変わる——これが圧縮の面白いところです。
選択肢の確認
1．○ ααα+βαβαβα = ααα+γγγ。
2．× 最後はβαで終わるのでγ。αは残らない。
3．× βが単独で残る位置はない(βの直後には必ずαがある)。
4．× αは先頭に3つ連続している。1つではない。
ここだけは覚えよう
繰り返しパターンの置き換え=圧縮の基本 — 左から順に区切って、機械的に置き換える。