T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS Python のおさらい(14)pset3の問題3の前ふり

<<   作成日時 : 2015/09/18 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

コンピュータサイエンスとプログラミング入門(Part1)の"Problem Set 3_Problem 3."前ふりを訳していきたいと思います。どうもこれを理解しないと問題3に行けないような気がしますので、、

-----------------------------------------------------------

The function you wrote in Problem 2 will find exact matches of a key string in a target string.

問題2で書いた関数は、キー文字列の完全一致を目標文字列中に発見する。

It is often also useful to find near matches, for example, matches of a key string in a target string, where one of the elements of the key string is replaced by a different element.

これは、キー文字列の一部を置き換えて、例えば目標文字列内の合致を見付けるような近似検索にしばしば便利なことがある。

For example, if we want to match ATGC against ATGACATGCACAAGTATGCAT, we know there is an exact match starting at 5 and a second one starting at 15.

たとえば、ATGACATGCACAAGTATGCAT に対して ATGC を比べたいならば、インデックス 5 から始まる完全一致とインデックス 15 から始まる第2のものあるということを、知っている。

However, there is another match starting at 0, in which the element A is substituted for C in the key, that is we match ATGC against the target.

しかし、キー文字列の C を A で置き換えると、 ATGC のキー(実際には ATGA)に対してインデックス 0 から始まる合致があることがわかる。 

Similarly, the key ATTA matches this target starting at 0, if we allow a substitution of G for the second T in the key string.

同様に、キー文字列の2番目の T を G に置き換えると、キー文字列 ATTA(実際には ATGA)に対してインデックス 0 から始まる合致があることがわかる。

画像




訳注:上に書かれていることは当たり前の事実ですが、近似検索を想定すると、1文字違っただけで始点がずいぶんと違ってしまうということを問題視しているようです。

We can build on your function from Problem 2 to solve this problem.

この問題を解決する方法は、問題2から得た関数を基に構築することができる。

In particular, consider the following steps.

特に、以下のステップを考慮せよ。

First, break the key string into two parts (where one of the parts could be an empty string).

はじめに、キー文字列を(ひとつの部分は空の文字列の可能性もありえる)二つの部分に分けよ。

Let’s call them key1 and key2.

これらを、 key1 と key2 と呼ぼう。

For each part, use your function from Problem 2 to find the starting points of possible matches, that is, invoke
starts1 = subStringMatchExact(target,key1)
and
starts2 = subStringMatchExact(target,key2)

starts1 = subStringMatchExact(target,key1) と starts2 = subStringMatchExact(target,key2) のように開始点を見付けるため問題2の関数を使用せよ。

The result of these two invocations should be two tuples, each indicating the starting points of matches of the two parts (key1 and key2) of the key string in the target.

二つの実施結果はタプルでなければならず、各々が目標文字列の中の二つのキー文字列(key1とkey2)の始点を示している。

For example, if we consider the key ATGC, we could consider matching A and GC against a target, like ATGACATGCA (in which case we would get as locations of matches for A the tuple (0, 3, 5, 9) and as locations of matches for GC the tuple (7,).

たとえば、キーをATGCとすると、ATGACATGCA のような目標文字列に対し、キーの一部の A および GC の開始点を考えることができる。このケースだと、A に対してはタプル (0, 3, 5, 9) 、GC に対してはタプル (7,)を得るだろう。 

画像

Of course, we would want to search over all possible choices of substrings with a missing element: the empty string and TGC; A and GC; AT and C; and ATG and the empty string.

もちろん、なくなった要素で部分文字列のすべてのありうる選択について捜したい:
空の文字列とTGC ;

画像

AとGC ;

画像

ATとC ;

画像



そして、ATGと空の文字列。

画像

Note that we can use your solution for Problem 2 to find these values.

これらの値を見つけるためにProblem 2の関数を使うことができることに注意。


Once we have the locations of starting points for matches of the two substrings, we need to decide which combinations of a match from the first substring and a match of the second substring are correct.

一度、2つの部分文字列の合致始点を得たならば、最初の部分文字列の合致と第2の部分文字列の合致のどの組合せが正しいか決める必要がある。

There is an easy test for this.

これに対する簡単な検査がある。

Suppose that the index for the starting point of the match of the first substring is n (which would be an element of starts1), and that the length of the first substring is m.

最初の部分文字列の始点のインデックスが(starts1の要素である)nで、最初の部分文字列の長さがmであるとする。

Then if k is an element of starts2, denoting the index of the starting point of a match of the second substring, there is a valid match with one substitution starting at n, if n+m+1 = k, since this means that the second substring match starts one element beyond the end of the first substring.

そして、k がstarts2の要素、つまり第2の部分文字列の始点のインデックスならば、始点が n の代理で明確な合致があり、n+m+1 = k ならば、2番目の文字列は、最初の部分文字列の最後を超えて始まっていることになる。

訳注:やはり例を示さないと分かり難いですね。以下で考えてみたいと思います。
AとGC の例では
画像

n = 0, 3, 5, 9  m = 1  k = 7
条件 n + m + 1 = k が成立するのは n = 5

空の文字列とTGC の例では
画像


n = 0, 1, 2, 3, 4, 5, 6, 7, 8  m = 0  k = 6
条件 n + m + 1 = k が成立するのは n = 5

ATとC の例では
画像

n = 0, 5  m = 2  k = 4, 8
条件 n + m + 1 = k が成立するのは n = 5

ATGと空の文字列 では
画像  
n = 0, 5  m = 3  k = 0, 1, 2, 3, 4, 7, 8
条件 n + m + 1 = k が成立するのは n = 0, 5
この例はあまり良くなかったかも知れません。

-----------------------------------------------------------

今日はこの辺で。。



テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
Python のおさらい(14)pset3の問題3の前ふり T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる