課題

距離行列から系統樹を表示するプログラムを作成せよ．

対象

プログラミングの経験のある学生．

期限・提出方法

気分が向いたら，７月１日２１：００までに加藤まで電子メールで提出せよ．提出方法は後日通知する．

原理

Neiｇhbor Joining 算法に関する資料．

詳細

You will be informed what have to be written in your report. The following is a tentative plan.

まず，ここから雛形dendro-teamname.tgzをダウンロードせよ．この雛型には次の４つのクラスが含まれている．

NjTest1.java から次のようにそれぞれのクラスを使ってプログラム全体が動く仕組みになっている．

public class NjTest1 {
	public static void main( String[] args ){
		// 対称な距離行列
		double[][] disttab = new double[][]{{0.00, 0.30, 0.20, 0.50},
			 {0.30, 0.00, 0.30, 0.40},
			 {0.20, 0.30, 0.00, 0.50},
			 {0.50, 0.40, 0.50, 0.00}};
		// 対称な距離行列 disttab から Neighbor Joining 算法を使って系統樹を計算する
		// 具体的には，各辺の始点と終点と長さを計算する．
		// ただし，disttab が　M x M とすると，ノード数は 2*M-1 になる．
		// ノード番号は， 0,..,M-1 が葉，2*M-2 が根，M,...,2*M-3 がそれ以外のノードに割り当てる．
		NeighborJoiningAlgo nj = new NeighborJoiningAlgo( disttab );
		// 系統樹の各辺の始点と終点と長さから各ノードの座標を割り当てる．
		// ただし，根の x 座標は 0 とし，
		//       x 座標の最大値 = 根から各葉までの距離のうち最大の値
		//       y 座標は 0 以上，M-1 以下の値を割り当てること．
		DendroNodePosAssigner npa = new DendroNodePosAssigner( nj.i1s(), nj.i2s(), nj.weis() );
		// 系統樹の辺の始点，終点，長さ，および各ノードの座標から系統樹を画面上に表示する．
		newwr(  nj.i1s(), nj.i2s(), nj.weis(), npa.xs(), npa.ys() ); 
	}
}

          

(1) このうち，DendroNodePosAssigner と NeighborJoiningAlgo は不完全なプログラムになっている．これを完成させよ．tar で固めて提出せよ．提出前に，次の手順で動作することを確認すること．

tar xzf dendro-[teamname].tgz
cd dendro-[teamname]/
javac NjTest1.java
java NjTest1

仕様の例はこちらだが，仕様を逸脱しても良い．クラス名は勝手に変えてもよい．

readme.txt には，工夫した点，拡張した点などアピーリングなポイントがあれば書いてください．たとえば，

• NeighborJoining 算法以外の方法も選択できるようにした．
• 樹形図の葉に名前をつけられるようにした．
• 樹形図のノードをクリックしたら２つの子ノードの位置が入れ替わるようにした．
• 樹形図の色を変えられるようにした．
• 作成した樹形図の画像を保存できるようにした．など．

(2) Gather some data, design a distance function (if needed), and make a dendrogram of the data.

The class DendroViewer can be tested by the following code:

NjTest2.java

public class NjTest2 {     public static void main( String[] args ){         int[]    i1s = new int[]{4,4,5,5,6,6};         int[]    i2s = new int[]{0,2,1,4,3,5};         double[] weis = new double[]{0.1,0.1,0.1,0.1,0.15,0.15};         double[] xs   = new double[]{0.35,0.25,0.35,0.15,0.25,0.15,0.0};         double[] ys   = new double[]{0.0,2.0,1.0,3.0,0.5,1.25,2.125};         new DendroViewer( i1s, i2s, weis, xs, ys );     } }

If you execute this code, you will see the tree below:

The numeric values in NjTest2.java are also a solution that should be produced by NeighborJoiningAlg and DendroNodePosAssigner.

問い合わせ先

• 加藤毅