最長共通部分列問題 トレースバックアプローチ

ウィキペディア

最長共通部分列問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/02/01 15:08 UTC 版)

トレースバックアプローチ

最長共通部分列のテーブルにおいて、最長共通部分列の行の計算に唯一要求されるのは、現在の行と次の行である。なお、長い配列の場合、それらの配列はおびただしく長くなるので、たくさんの記憶領域が要求される。記憶領域を節約するには、実際の部分列を保存しない事である。しかし、部分列の長さと方向矢印は保存する必要がある。それは、以下のテーブルのようにである。

Storing length, rather than sequences

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	0	0	0	0	0	0
1	G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
2	A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
3	C	0	${\overset {\ \uparrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2

実際の部分列は、”トレースバック”手順で推測する。それは続く逆向き矢印であり、テーブルの最後のセルから開始する。トレースバックでは長さは減少する。配列に必須なのは共通の要素である。いくつかの経路が可能であり、その場合、セルに二つの矢印がある。以下は、その解析のためのテーブルである。セルの色の付いた数字は減少についての長さである。太字の数字はトレースした配列 (GA) である。

Traceback example

		0	1	2	3	4	5
		Ø	A	G	C	A	T
0	Ø	0	0	0	0	0	0
1	G	0	${\overset {\ \ \uparrow }{\leftarrow }}$0	${\overset {\nwarrow }{\ }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1	${\overset {\ }{\leftarrow }}$1
2	A	0	${\overset {\nwarrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ }{\leftarrow }}$2
3	C	0	${\overset {\ \uparrow }{\ }}$1	${\overset {\ \ \uparrow }{\leftarrow }}$1	${\overset {\nwarrow }{\ }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2	${\overset {\ \ \uparrow }{\leftarrow }}$2