平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－1/9

生物工学 Ⅱ次の[Ⅱ‐１]～[Ⅱ‐３]の３題を，それぞれ別の解答用紙に答えよ．

[Ⅱ‐１]
DNA シークエンシング技術の発達により，500〜700 塩基程度の長さの DNA 断片の塩基配列をほぼ自動的に決定し，得られたデータから計算機を用いてゲノム全体を再構築できるようになった．
得られた塩基配列は国際塩基配列データベースに登録され，誰でも制限なしに利用可能となっている．2012 年 6 月現在，国際塩基配列データベースに登録されている全てのエントリの合計塩基数は1400 億を超えており，その中から特定の塩基配列を探索することは，計算機の利用なくしてはほぼ不可能である．
塩基配列は，数種類の文字種からなる文字列として表現することができるため，塩基配列の探索には，計算機による文字列探索技術が適用できる．計算機による文字列探索とは，テキストと呼ばれる長さ n の文字列と，パターンと呼ばれる長さ m の文字列が与えられたときに，テキスト中にパターンが現れるかどうかを判定し，現れる場合には，テキスト中でパターンが始まる位置を求める処理である．本問では，テキストはパターンよりも長く， n  m であるとする．
以下では，テキストおよびパターンの各文字を Ti および Pi として表す．長さ n のテキストは

T1T2  Tn ，長さ m のパターンは P1 P2  Pm と表される．テキストの i 番目の文字からパターンを照合する場合の，テキストとパターンの対応関係を図 1 に示す．また文字種は断りのない限り A, G, C,T の 4 種類であるとする．
先頭
テキスト
（長さn）

T1

探索位置

T2...

Ti 1

パターン
（長さm ）末尾Ti

Ti 1...

Ti  m 1

P1

P2...

Pm...

Tn

図1（問１） 最も単純な文字列探索方法として，力まかせ法と呼ばれる手法がある．力まかせ法では，
まずテキスト内にパターンの最初の文字 P1 が出現する位置を，テキストを先頭から 1 文字ずつ

P1 と照合して探索する．テキストの i 番目の文字 Ti が P1 と一致した場合，続いて Ti 1 から Ti  m 1 までの文字が，それぞれ P2 から Pm と一致するかを順次照合する．途中で不一致が生じた場合，以降の照合を中止し，文字 P1 の探索をテキストの i  1 番目の文字 Ti 1 から再開する．パターンの文字が対応するテキストの文字と全て一致した場合，パターンが発見できたことになる．
（次のページに続く）

平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－2/9（ア） 力まかせ法を用いてテキスト GTCGATGTGCGTGCACGG からパターン GTGCAC を発見するまでの文字照合過程を全て示し，文字照合回数と，そのうち文字が一致した回数を答えよ．
（イ） 力まかせ法を用いて，長さ n  10 のテキストから長さ m  5 のパターンを探索する場合に，文字照合回数が最大となるテキストとパターンの組み合わせを一つ示せ．ただし，テキストの部分文字列 T6T7T8T9T10 がパターン P1 P2 P3 P4 P5 と一致するものとする．テキストとパターンのいずれも，4 種類の文字種を全て含んでいる必要はない．
（問２） 力まかせ法では，テキストのある位置からパターンを照合した結果が不一致であった場合に，探索位置を 1 文字だけ末尾の方に移動させる．これに対して，テキストのある位置からパターンを照合する際に，パターンの末尾の文字から照合を行うと，不一致が生じた場合に，パターンに関する知識に基づいて探索位置を一度に大きく移動させることができ，文字照合回数の削減が期待できる．この方法を本問では末尾探索法と呼ぶ．
例として，テキスト ATGAGTGATGTA から，パターン CCC を探索する事例 1 を考える．力まかせ法と同様に，探索位置はテキストの先頭から末尾に向かって移動させる．最初に T1T2T3（ATG）と P1 P2 P3 （CCC）を照合するが，力まかせ法と異なり，まずパターンの末尾の文字 P3（C）を T3（G）と照合する．T3（G）と P3（C）が異なることから，T1T2T3（ATG）は P1 P2 P3（CCC）と一致しないことが 1 文字の照合で確定する．加えて，T3 すなわち G はパターン P1 P2 P3（CCC）
中に出現しないことに着目すると，T3 を含むテキストの部分文字列がパターンと一致する可能性はないことも判明する．よって，次は（1○）と P1 P2 P3 の照合まで探索位置を移動させることができる．
別の例として，事例 1 と同じテキストから，パターン GCC を探索する事例 2 を考える．事例 1 と同様に， T3 （G）と P3 （C）が異なることから T1T2T3 （ATG）は P1 P2 P3 （GCC）と一致しないことが確定する．事例 1 との違いは， T3 すなわち G がパターン P1 P2 P3 （GCC）に含まれているため，T3 とパターン内の G が対応する探索位置で，テキストの部分文字列とパターンが一致する可能性がある点である．したがって次は（2○）と P1 P2 P3 を照合する必要があることがわかる．
以上の事例を参考にすると，末尾探索法の戦略の一つとして，不一致が生じたテキストの文字に着目し，その文字に一致するようにパターンの移動量を決定する方法が考えられる．具体的には，テキストの部分文字列 TiTi 1  Ti  m 1 とパターン P1 P2  Pm の照合において，不一致がパターンの先頭から j 文字目の照合，すなわち Pj と Ti  j 1 の照合で生じたとすると，パターンの不一致位置より先頭側の部分文字列 PP
1 2  Pj 1 において Ti  j 1 と一致する最後の文字が， Ti  j 1と比較されるように探索位置を移動すればよい．つまり，Ti  j 1  Pk (1  k  j  1) となる最大の3k を発見し，探索位置を（ ○）文字だけ末尾の方に移動させる．また，そのような k が存4在しない場合には，探索位置を（ ○）文字だけ末尾の方に移動させる．

（ア） 末尾探索法により文字照合回数の削減が期待できることを，次のようなテキストとパターンを用いて確認してみる．この小問（問２（ア））においてのみ文字種を 26 種類とする．
テキスト ABCDEFGHIJKLMNOPQRSTUVWXYZ にパターン ZZZZZZ が含まれていないことを判定するために照合されるテキストの文字を，照合された順に全て挙げよ．
（次のページに続く）

平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験（イ） （1○）および（生物工学Ⅱ－3/92○）に入るテキストの部分文字列を，以下の(a)〜(d)の中からそれぞれ一つ選択せよ．
(a) T2T3T4（ウ） （3○(b) T3T4T54）および（ ○(c) T4T5T6(d) T5T6T7）に入る式を i, j , k および数字を用いて書け．

（エ） 末尾探索法を用いてテキスト GTCGATGTGCGTGCACGG からパターン GTGCAC を発見するまでの文字照合過程を全て示し，文字照合回数と，そのうち文字が一致した回数を答えよ．
（オ） 末尾探索法を用いて，長さ n  10 のテキストから長さ m  5 のパターンを探索する場合に，文字照合回数が最大となるテキストとパターンの組み合わせを一つ示せ．ただし，テキスト内にパターンは含まれていないものとする．テキストとパターンのいずれも，4 種類の文字種を全て含んでいる必要はない．
（カ） 末尾探索法においてパターンに関する知識を利用するための別の戦略として，テキストとパターンの不一致が生じた場合に，それまで一致していた部分に関する情報を利用して，探索位置の移動量を決定する方法も考えられる．テキストの部分文字列 TiTi 1  Ti  m 1 とパターン P1 P2  Pm の照合において，不一致がパターンの先頭から j 文字目の照合，すなわち Pj とTi  j 1 の照合で生じたとして，この戦略の具体的なアルゴリズムを設計せよ．

平成年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－［Ⅱ‐２］に示す剛体が平面内を 軸方向へ転がる運動を考える．図の剛体は，厚さを無視で図きる半径 の円環であり，その質量を とする．図の剛体はリムレスホイールと呼ばれるもので，厚さを無視できる半径 の円環に，その中心から放射状に広がる長さ の細いスポークが取り付けられている．ここでは，そのスポークを脚と呼び，隣り合う脚の成す角をとする．脚の数を とすると，であり，図はの例である．円環部分の質量を とし，脚の太さおよび質量は無視できるとする．地面に接し，その接点が回転の軸になる脚を支持脚と呼び，その他の脚を遊脚と呼ぶ．
なお，重力加速度を とする．また， つの円環の密度は一様とする．このとき，以下の設問に答えよ．

図（問 ） 図のような水平面上の円環の運動について，円環は平面上を滑らず，また摩擦によるエネルギーの損失なく転がるとき，次の ア から エ の空欄にあてはまる値もしくは式を答えよ．
円環の中心まわりの慣性モーメントを， ， を使って表すと，
アである．時刻 での円環の角速度をとする．

に関する運動方程式は，イである．したがって，における角速度を軸方向の速さは，それぞれ，ウとすれば，時刻 での角速度と円環の中心のエである．
（問 ） 図のような水平面上のリムレスホイールの運動において，支持脚は平面上を滑らず，また摩擦によるエネルギーの損失はないとする．また，遊脚が接地するとき，完全非弾性衝突が起こり，瞬時に遊脚から支持脚および支持脚から遊脚への遷移が起こるとする．支持脚が平面の法線方向と成す角を 時計回りを正とする とするとき，次の オ から シ の空欄にあてはまる値もしくは式を答えよ．

次のページに続く

平成年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－

図
図の上段のように，時刻において点を使って表すと，モーメント を，を支持脚の接点とする．点まわりの慣性オとなる．時刻において，点のまわりに角速度を与える．角速度は，リムレスホイー
ルが時計回りにしばらく回転するのに十分な大きさであるとし，遊脚から支持脚への遷移が起こるの中段のように，で遊脚から支持脚への最初の遷移が点際の角速度の変化を考える．図で起こるとする．エネルギー保存の法則により，での点まわりの角速度は カ である．遊脚が点に接地する直前において，点をリムレスホイールの回転軸と考えたとき，点まわりの重心の角運動量は キ であり，重心まわりの角運動量は ク である．このとき，リムレスホイールの全角運動量は，ケである．一方，点は，角運動量に接地した直後の点まわりの角速度をとすると リムレスホイールの全コ

次のページに続く

平成年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験となる．したがって，角運動量保存の法則により，と生物工学Ⅱ－の関係は，サとなる．さらに，リムレスホイールの回転に伴い遊脚が接地する点を順に，する 点において遊脚が支持脚に遷移した直後の点まわりの角速度をととすると，シとなる．
（問 ） 図のように，リムレスホイールが水平面と角度 を成す無限に続く斜面を転がる運動を考える．前問で考えたように，リムレスホイールが水平面を転がる場合は，ステップ数 に対して角速度は指数関数的に減少する．しかし，斜面を下る場合は，重力の作用により ステップあたりの平均速度が一定の運動が可能になる．このような運動について，次の ス から チ の空欄にあてはまる値もしくは式を答えよ．以下では，角度 と は十分小さく，，，と近似できるものとする．
時刻 において点を接点とする支持脚が斜面の法線方向と成す角をついての運動方程式は， と について線形近似すると，とするとき，にスとなる．ここで，はまわりの慣性モーメントである．この運動方程式において，を満たす解は，セである．リムレスホイールの回転に伴い遊脚が接地する点を順に，とする 点から点へ脚が運ばれる時間間隔が一定値 であるとき，遊脚が支持脚に遷移した直後の支持脚まわりの角速度がであると仮定する．さらに，図の上段のように，で支持脚が点にあるとき，すでにこのような周期的な運動が実現されているとする．この運動状態が実現するの中段のように遊脚が点に接地する直前において，ためには，図ソとなる必要がある．これらの条件を満たすは，タとなる．したがって，リムレスホイールの平均の速さは，チとなる．

平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－7/9[Ⅱ‐３]
画像を用いた距離計測に関連する以下の問いに答えよ．
（問１） カメラ 2 台を光軸が平行になるように並べ，二眼ステレオ法により物体までの距離計測を行うパッシブステレオ法について考える．
2 台のカメラの光軸は z 軸と平行とする．カメラに入射する全ての光線は，それぞれのカメ
ラの光学中心 OL (b / 2, 0, 0) および OR (b / 2, 0, 0) を通る（ピンホールカメラモデル）．撮像面は，一般的には z  0 の領域に配置されるが，像が反転してわかりにくいため，撮像面を各々の光学中心に対して点対称に折り返し，図 1 のように平面 z  f の上に配置する．撮像面 S L およびS R の中心は，それぞれ (b / 2, 0, f ) および (b / 2, 0, f ) である． b は基線長， f は焦点距離と呼ばれ，いずれも正の値である．光学中心 OL と撮像面 S L の組，および，光学中心 OR と撮像面 S Rの組から構成されるカメラを，それぞれカメラ C L およびカメラ C R と呼ぶ．

z

光軸

光軸

P( x0 ,0, z0 )yuuuLvvuRf撮像面 S L
OLO

撮像面 S RORx

図1（ア） ピンホールカメラモデルでは，空間内の点は，点とカメラの光学中心とを結ぶ直線と，撮像面との交点に投影される．撮像面 SL および SR の大きさを幅 dw ，高さ dh とし，それぞれの撮像面上に，図 1 のように二次元座標系 uv を取る．点 P( x0 , 0, z0 ) が，撮像面 SL および SRに投影される点の u 座標 uL および uR を， x0 , z0 , b, f , d w を用いて表せ．
（イ） ある点が二つの撮像面それぞれに投影された際の，撮像面上での位置の差を視差 D とし，

D  uL  uR と定義する．対象物までの距離 z0 を視差 D から求める式を書け．
（ウ） 一般的に，画像から求めた視差には，計測に伴う誤差が含まれる．視差に誤差 D が生じた際に，距離の真値が z  z0 である点の z 座標（奥行き）の推定値に生じる誤差を，b, f , z0 , D を用いて表せ．ただし， D  D とする．
（エ） パッシブステレオ法の奥行き分解能を向上させるために考えられる方法と，その方法により分解能が向上する理由について述べよ．また，そのときに生じる欠点について述べよ．
ただし，撮像面に配置される撮像素子の性質（解像度および画素数）は変更できないものとする．
（次のページに続く）

平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－8/9（オ） ヒトが網目のような規則的な模様を持つ物体を見た場合に，実際の距離とは異なる距離に，物体があるように感じられることがある．この理由を，パッシブステレオ法の原理に基づき，図を用いて説明せよ．
（問２） 問１（オ）で見られるパッシブステレオ法の問題点を解決する方法として，以下に述べるアクティブステレオ法がある．
まず，問１のカメラ CL を取り除き，点 OL (b / 2, 0, 0) に点光源を，撮像面 SL があった位置にスライド面 SL を置く．スライド面 SL の中心は ( b / 2, 0, f ) である（図 2）．スライド面上には投影パターンが設定され，光が透過できる領域を限定する．点光源から発してスライド面を通過した光は，スライド面上に設定された投影パターンを，計測対象に投影する．点光源とスライド面の組によって構成される投影装置をプロジェクタと呼ぶ．プロジェクタによりパターンが投影された計測対象を，カメラ CR で撮像し，スライド面 SL 上の位置とカメラ CR の撮像面 S R 上の位置を対応付けることにより，パッシブステレオ法と同じ原理に基づく距離計測が可能となる．
（ア） スライド面の大きさを幅 dw ，高さ dh とし，スライド面上に，図 2 のように二次元座標系uv を取る．
スライド面は格子状の画素に区切られており，画素単位で投影パターンを設定できる．横方向の画素数を W ，縦方向の画素数を H とする．スライド面左上の画素を画素 (0, 0) とし，その画素から数えて横方向に i 画素，縦方向に j 画素進んだ位置にある画素を画素 (i, j ) と表記する．図 2 左上にスライド面 SL 上の画素配置を示す．このとき，画素 (i, j ) の中心の uv 座
標を求めよ．

dw
スライド面 S L
拡大図(0,0)dhz

光軸(W  1, H  1)

光軸

yu

u
uLvv

uRf

スライド面 S LOLO

撮像面 S R
ORx

図2
（次のページに続く）

平成 25 年度大阪大学大学院基礎工学研究科博士前期課程（一般）入学試験

生物工学Ⅱ－9/9（イ） スライド面の横方向の画素数 W および縦方向の画素数 H を 256 とする．計測対象に対して，画素 (163,128) のみを光が通過するスポット光パターンを投影したところ，カメラ C R の光軸上の点が明るくなった（すなわち uR  d w / 2 である）
．撮像面およびスライド面の幅 dwが 15mm，焦点距離 f が 20mm，基線長 b が 100mm のとき，スポット光が投影された点の z座標を求めよ．
（ウ） スライド面の縦一列の画素のみを透過して投影されるパターン光を，スリット光と呼ぶ．
図 3 上に示す 5 種類のスリット光を計測対象に投影し，カメラ C R で取得した画像を図 3 下に示す．これらの結果から，計測対象物体の形状についてわかることを述べよ．

図3（問３） ヒトが視覚から周囲の空間の奥行きや三次元構造を把握する上では，様々な手掛かりを用いている．前問までで取り扱ったステレオ法は両眼視差の利用に相当する．奥行き感をもたらす視覚系の手掛かりを両眼視差以外に三種類挙げ，それぞれが奥行きの把握にどのように寄与しているかを説明せよ．