臺灣博碩士論文加值系統

近三十年來，隨著計算機科學、電機與計算機工程及作業研究等領域的成長，圖形理論也呈現出爆炸性的發展，而其中支配相關問題可能是圖形理論中發展最為快速的。特別的是，從演算法角度去觀察支配相關問題的文獻在這其中佔了相當重要的比例。支配問題的概念其實也就是許多在作業研究的地域問題的模型。而根據許多在應用方面不同的需要，漸漸衍生出許多對應的支配相關問題樣式。在這篇博士論文中，我們將以電力支配問題、森林生成k 樹以及網路比對問題來做具體的討論。
我們可以根據監管的規則將電力網路系統的監測問題化成圖論上的電力支配問題。由於一個電力支配集合具有傳遞監測的能力，使得目前這個問題只有在樹狀相關圖形上有多項式時間的演算法。所以我們希望能夠在別的特殊圖形上設計出有效率的演算法或是探討它的問題複雜度。在這篇論文中，我們在間隔圖及環狀圖上提出了線性時間的演算法，並證明電力支配在分裂圖上是NP 完備的。
在沒有加權的圖形中，森林生成k 樹跟k 距離支配問題是完全等價的。在過去的幾年中被廣泛探討的森林生成星狀圖其實就是森林生成1 樹(k=1)。森林生成星狀圖問題是來自於比較基因學中的一個很重要的問題：多重序列基因比對。我們在這篇論文中分別針對森林生成k 樹在無向和有向的加權圖上都提出(k/k+1)的近似演算法。
最後我們更進一步把圖論中支配問題的觀念推廣到生物資訊中常用到的星狀比對方法。我們將這個觀念應用到系統生物學中多重蛋白質交互作用網路比對的問題。多重蛋白質交互作用網路比對問題的動機是因為我們想要能夠在這些以細胞為單位的大型系統中，找出各種生物之間蛋白質基因演化的過程。我們提出的星狀比對方法配合上光譜圖論群集演算法，使得我們在五個真核生物的多重蛋白質交互作用網路比對中，不論在結果一致性和覆蓋性都凌駕於目前現在所有的演算法。

Within the last thirty years, concurrent with the growth of such areas as computer science, electrical and computer engineering, and operations research, graph theory has seen explosive growth and perhaps the fastest-growing area within graph theory is the study of domination and related problems. In particular, there has appeared a significant portion of literature from an algorithmic point of view. The concept of domination in graph theory is a natural model for many location problems in operations research. According to different requirements for practical applications, there are various types of domination problem. In this dissertation we specifically consider power domination, spanning k-tree forest, and network alignment problem.
The power system observation problem can be transformed into the graph-theoretic power domination problem according to the observation rules. Since a power dominating set has the capability of observing remote elements via propagation,
there are only polynomial time algorithms for power domination problem on tree-type graphs. We would like to design efficient polynomial algorithms and investigate the
problem complexity for power domination problems on other special graph classes. We show that the problem of finding the power domination number for split graphs is NP-complete. In addition, we present a linear time algorithm for an interval graph, if the interval ordering of the graph is provided, and show that the same result holds for the class of circular-arc graphs.
For unweighted graphs, the spanning k-tree forest problem is equivalent to the k-distance domination problem. The spanning 1-tree forest problem has been known as the spanning star forest problem and investigated extensively in the past several years. This problem arises from aligning multiple genomic sequences, a basic bioinformatics task in comparative genomics. We show that this generalization of the spanning star forest, the spanning k-tree forest problem, can be (k/k+1)-approximated in polynomial time for both undirected and directed weighted graphs.
Furthermore we extend the domination in graph theory to the star aligned method in bioinformatics, which is applied to multiple protein-protein interaction network alignment problem in system biology field. The search for such a network alignment is motivated by the intuition that evolution of genes happens within the context of the
larger cellular system. We present our star aligned algorithm based on spectral clustering, which outperforms existing algorithms for global network alignment in
coverage and consistency of the five available eukaryotic networks.

Contents
1 Introduction 3
1.1 Power domination problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Spanning k-tree forest problem . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Multiple network alignment problem . . . . . . . . . . . . . . . . . . . . . . 16
2 Power domination problem 20
2.1 NP-completeness results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Power dominating set for interval graphs . . . . . . . . . . . . . . . . . . . . 23
2.3 Power dominating set for proper circular-arc graphs . . . . . . . . . . . . . . 38
2.4 Power dominating set for circular-arc graphs . . . . . . . . . . . . . . . . . . 43
2.5 Discussion and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3 Spanning k-tree forest problem 52
3.1 Spanning k-tree forest problem . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.1 Maximum spanning k-tree forest for trees . . . . . . . . . . . . . . . . 52
3.1.2 A k
k+1-approximation algorithm for general graphs . . . . . . . . . . . 55
3.2 Approximation algorithmfor directed graphs . . . . . . . . . . . . . . . . . . 57
3.3 The weighted distancemodel . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4 Discussion and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 Multiple network alignment problem 62
4.1 Star spread and spectral partition . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 Discussion and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5 Concluding remarks 73

[1] A. Aazami and M.D. Stilp. Approximation algorithms and hardness for domination
with propagation. In Proceedings of the 10th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems, APPROX’07, (2007) pp. 1–15.
[2] R. Anderson, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors.
In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science,
FOCS’06, (2006) pp. 475–486.
[3] M. Ashburner et al. Gene ontology: tool for the unification of biology. The gene ontology
consortium. Nature Genetics, 25, (2000) pp. 25–29.
[4] T.L. Baldwin, L. Mili, M.B. Boisen, Jr., and R. Adapa. Power system observability with
minimal phasor measurement placewement. IEEE Trans. Power System, 8(2) (1993)
pp. 707–715.
[5] B.S. Baker. Approximation Algorithms for NP-complete problems on planar graphs.
Journal of the ACM, 41(1) (1994) pp. 153–180.
[6] M. Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of 15th Annual
Symposium on theory of Computing, (1983) pp. 80–86.
[7] J. Berg and M. L‥assig. Cross-species analysis of biological networks by Bayesian alignment.
Proc. Natl. Acad. Sci. USA, 103, (2006) pp. 10967–10972.
[8] V. Berry, S. Guillemot, F. Nicolas, and C. Paul. On the approximation of computing
evolutionary trees. In Proceedings of the 11th Annual International Computing and
Combinatorics Conference, COCOON’05, (2005) pp. 115–125.
[9] F. Bock. An algorithm to construct a minimum directed spanning tree in a directed
network. Developments in Operations Research, Gordon and Breach, New York, (1971)
pp. 29–44.
[10] E. Boyle et al. GO:TermFinderXopen source software for accessing gene ontology information
and finding significantly enriched gene ontology terms associated with a list of
genes. Bioinformatics, 20, (2004) pp. 3710–3715.
[11] D.J. Brueni and L.S. Heath. The PMU placement problem. SIAM J. Discrete Math.,
19(3) (2005) pp. 744–761.
[12] P.M. Camerini, L. Fratta, and F. Maffioli. A note on finding optimum branchings.
Networks, 9 (1979) pp. 309–312.
[13] G.J. Chang. Algorithmic aspects of domination in graphs. In: Handbook of Combinatorial
Optimization (D.-Z. Du and P. M. Pardalos eds.), 3 (1998) pp. 339–405.
[14] G.J. Chang. Labeling algorithms for domination problems in sun-free chordal graphs.
Discrete Appl. Math., 22 (1988/89) pp. 21–34.
[15] D. Chakrabarty and G. Goel. On the Approximability of Budgeted Allocations and Improved
Lower Bounds for Submodular Welfare Maximization and GAP. In Proceedings
of the 49th IEEE Symposium on Foundations of Computer Science, FOCS’08, (2008)
pp. 687–696.
[16] N. Chen, R. Engelberg, C.T. Nguyen, P. Raghavendra, A. Rudra, and G. Singh. Improved
approximation algorithms for the spanning star forest problem. In Proceedings
of the 10th International Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, APPROX’07, (2007) pp. 44–58.
[17] X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z.Du. A polynomial-time approximation
scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks,
42(4) (2003) pp. 202–208.
[18] Y.J. Chu and T.H. Liu. On the shortest arborescence of a directed graph. Science Sinica,
14 (1965) pp. 1396–1400.
[19] E.J. Cockayne, S.E. Goodman, and S.T. Hedetniemi. A linear algorithm for the domination
number of a tree. Inform. Process. Lett., 4 (1975) pp. 41–44.
[20] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein. Introduction to Algorithms, 2nd
Edition, The MIT Press, (2001).
[21] P. Dorbec, M. Mollard, S. Klavˇzar, and S. ˇSpacapan. Power domination in product
graphs. SIAM J. Discrete Math., 22(2) (2008) pp. 554–567.
[22] M. Dorfling and M.A. Henning. A note on power domination in grid graphs, Discrete
Applied Math., 154(6) (2006) pp. 1023–1027.
[23] J. Dutkowski and J. Tiuryn. Identification of functional modules from conserved ancestral
protein-protein interactions. Bioinformatics, 23, (2007) pp. 149–158.
[24] J. Edmonds. Optimum branchings. J. Research of the National Bureau of Standards,
71B (1967) pp. 233–240.
[25] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4)
(1998) pp. 634–652.
[26] J.A. Flannick, A.F. Novak, C.B. Do, B.S. Srinivasan, and S. Batzoglou. Automatic
parameter learning for multiple network alignment. In Proceedings of the 12th International
Conference on Research in Computational Molecular Biology, RECOMB’08,
LNBI, 4955, (2008) pp. 214–231.
[27] H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set
union. Journal of Computer and System Sciences, 30(2) (1985) pp. 209–221.
[28] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness, Freeman, (1979).
[29] M.C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Academic Press, Inc.
(1980).
[30] J. Guo, R. Niedermeier, and D. Raible. Improved algorithms and complexity results for
power domination in graphs, Algorithmica, 52(2) (2008) pp. 177–202.
[31] J.-D. Han, D. Dupuy, N. Bertin, M.E. Cusick, and M. Vidal. Effect of sampling on
topology predictions of protein-protein interaction networks. Nature Biotech., 23, (2005)
pp. 839–844.
[32] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning. Domination
in graphs applied to electric power networks. SIAM J. Discrete Math., 15(4) (2002)
pp. 519–529.
[33] T.W. Haynes, S.T. Hedetniemi and P.J. Slater. Domination in Graphs: The Theory,
Marcel Dekker, Inc. New York (1998).
[34] T.W. Haynes, S.T. Hedetniemi and P.J. Slater. Domination in Graphs: Advanced Topics,
Marcel Dekker, Inc. New York (1998).
[35] J. H˚astad. Some optimal inapproximability results. J. ACM, 48 (2001) pp. 798–859.
[36] M.A. Henning, O.R. Oellermann, and H.C. Swart. Bounds on distance domination parameters.
J. Combin. Inform. System. Sci., 16 (1991) pp. 11–18.
[37] M.A. Henning, O.R. Oellermann, and H.C. Swart. The diversity of domination. Discrete
Math., 161 (1996) pp. 161–173.
[38] D.S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems.
SIAM Journal on Computing, 11(3) (1982) pp. 555-556.
[39] D.S. Hochbaum and W. Maass. Approximation schemes for covering and packing problems
in image processing and VLSI. J. ACM, 32 (1985) pp. 130–136.
[40] W.-L. Hsu, and K.-H. Tsai. Linear time algorithms on circular-arc graphs. Inform.
Process. Letters, 40(3) (1991) pp. 123–129.
[41] H. Huang, B.M. Jedynak, and J.S. Bader. Where have all the ineractions gone? Estimating
the coverage of two-hybrid protein interaction maps. PLoS Comput. Bio., 3,
(2007) pp. 2155–2174.
[42] T.J. Hubbard et al. Ensembl 2007. Nucleoc Acids Res., 35, (2007) pp. 610–617.
[43] T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki. A comprehensive
two-hybrid analysis to explore the yeast protein interactome. Proc. Natl. Acad. Sci.
USA, 98, (2001) pp. 4569–4574.
[44] H. Jeong, S.P. Mason, A.-L. Barab′asi, and Z.N. Oltvai. Lethality and centrality in
protein networks. Nature, 411 (2001) pp. 41–42.
[45] D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer
and System Sciences, 9(3) (1974), pp. 256–278.
[46] M. Kalaev, V. Bafna, and R. Sharan. Fast and accurate alignment of multiple protein
networks. In Proceedings of the 12th International Conference on Research in Computational
Molecular Biology, RECOMB’08, LNBI, 4955, (2008) pp. 246–256.
[47] M. Kanehisa and S. Goto. KEGG: Kyoto encyclopedia of genes and genomes. Nucleoc
Acids Res., 28, (2000) pp. 27–30.
[48] M.-J. Kao and C.-S. Liao. Capacitated domination problem. In Proceedings of 18th
International Symposium on Algorithms and Computation, ISAAC’07, (2007) pp. 256–
267. Also accepted by Algorithmica, 2009.
[49] R.M. Karp. A simple derivation of edmonds’ algorithm for optimum branchings. Networks,
1 (1971) pp. 265–272.
[50] B.P. Kelley, R. Sharan, R.M. Karp, T. Sittler, D.E. Root, B.R. Stockwell, and T. Ideker.
Conserved pathways within bacteria and yeast as revealed by global protein network
alignment. Proc. Natl. Acad. Sci. USA, 100, (2003) pp. 11394–11399.
[51] B.P. Kelley, B. Yuan, F. Lewitter, R. Sharan, B.R. Stockwell, T. Ideker. Pathblast:
a tool for alignment of protein interaction networks. Nucleoc Acids Res., 32, (2004)
pp. 83–88.
[52] W.J. Kent, C. Riemer, L. Elnitski, A.F. Smit, K.M. Roskin, R. Baertsch, K. Rosenbloom,
H. Clawson, E.D. Green, D. Haussler, and W. Miller. Aligning multiple genomic
sequences with the threaded blockset aligner, Genome Research, 14 (2004), pp. 708–715.
[53] M. Koyuturk, A. Grama, and W. Szpankowski. Pairwise local alignment of protein
interaction networks guided by models of evolution. In Proceedings of the 9th International
Conference on Research in Computational Molecular Biology, RECOMB’05,
LNBI, 3500, (2005) pp. 48–65.
[54] J. Kneis, D. M‥olle, S. Richter, and P. Rossmanith. Parameterized power domination
complexity. Inform. Process. Letters, 98(4) (2006) pp. 145–149.
[55] N.J. Krogan et al. Global landscape of protein complexes in the yeast Saccharomyces
cerevisiae. Nature, 440, (2006) pp. 4412–4415.
[56] D.T. Lee, M. Sarrafzadeh, and Y.F. Wu. Minimum cuts for circular-arc graphs. SIAM
J. Computing, 19(6) (1990) pp. 1041–1050.
[57] C.-S. Liao and G.J. Chang. Algorithmic aspect of k-tuple domination in graphs. Taiwanese
J. Math., 6 (2002) pp. 415-420.
[58] C.-S. Liao and G.J. Chang. k-tuple domination in graphs. Inform. Process. Letters,
87(1) (2003) pp. 45–50.
[59] C.-S. Liao and D.T. Lee. Power domination problem in graphs. In Proceedings of 11th
International Computing and Combinatorics Conference, COCOON’05, (2005) pp. 818–
828.
[60] C.-S. Liao and L. Zhang. Approximating the spanning k-tree forest problem. In Proceedings
of the third International Frontiers of Algorithmics Workshop, FAW’09, (2009).
[61] C.-S. Liao, K. Lu, M. Baym, R. Singh, and B. Berger. IsoRankN: Spectral methods for
global alignment of multiple protein networks. In Proceedings of the 17th International
Conference on Intelligent Systems for Molecular Biology, ISMB’09, (2009).
[62] D.J. Lipman, S.F. Altschul, and J.D. Kececioglu. A tool for multiple sequence alignment.
Proc. Natl. Acad. Sci. USA, 86, (1989) pp. 4412–4415.
[63] L. Lov′asz. On the ratio of optimal and fractional covers. Discrete Math., 13 (1975)
pp. 383–390.
[64] L.R. Matthews, P. Vaglio, J. Reboul, H. Ge, B.P. Davis, J. Garrels, S. Vincent, and M.
Vidal. Identification of potential interaction networks using sequence-based searches for
conserved protein-protein interactions or interologs. Genome Res., 11, (2001) pp. 2120–
2126.
[65] G.R. Mishra et al. Human protein reference database - 2006 update. Nucleoc Acids Res.,
34, (2006) pp. 411–414.
[66] C.T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller, and L. Zhang. Approximating
the spanning star forest problem and its applications to genomic sequence alignment.
SIAM J. Comput., 38 (2008) pp. 946–962. Also appeared in Proceedings of SODA’2007,
pp. 645–654.
[67] G. Ramalingam and C. Pandu Rangan. A unified approach to domination problems in
interval graphs. Inform. Process. Letters, 27(5) (1988) pp. 271–274.
[68] A. Schlicker, F.S. Domingues, J. Rahnenf‥uhrer, and T. Lengauer. A new measure for
functional similarity of gene products based on Gene Ontology. BMC Bioinformatics,
7, (2006) pp. 1–16.
[69] E. Segal, R. Yelensky, A. Kaushal, T. Pham, A, Regev, D. Koller, and N. Friedman.
GeneXPress: A Visualization and Statistical Analysis Tool for Gene Expression and Sequence
Data. In Proceedings of the 12th International Conference on Intelligent Systems
for Molecular Biology, ISMB’04, (2004) pp. 1–3.
[70] R. Sharan, S. Suthram, R.M. Kelly, T. Kuhn, S. McCuine, P. Uetz, T. Sittler, R.M.
Karp, and T. Ideker. Conserved patterns of protein interaction in multiple species. Proc.
Natl. Acad. Sci. USA, 102, (2005) pp. 1974–1979.
[71] R. Singh, J. Xu, and B. Berger. Pairwise global alignment of protein interaction networks
by matching neighborhood topology. In Proceedings of the 11th International Conference
on Research in Computational Molecular Biology, RECOMB’07 LNBI, 4453, (2007)
pp. 16–31.
[72] R. Singh, J. Xu, and B. Berger. Global alignment of multiple protein interaction networks
with application to functional orthology detection. Proc. Natl. Acad. Sci. USA,
105, (2008) pp. 12763–12768.
[73] P.J. Slater. R-Domination in Graphs. J. ACM, 23 (1976) pp. 446–450.
[74] C. Stark, B.-J. Breitkreutz, T. Reguly, L. Boucher, A. Breitkreutz, and M. Tyers.
BioGRID: a general repository for interaction datasets. Nucleoc Acids Res., 34, (2006)
pp. 535–539.
[75] R.E. Tarjan. Efficiency of a good but not linear set union algorithm, Journal of the
ACM, 22(2) (1975) pp. 215–225.
[76] R.E. Tarjan. Finding optimum branchings. Networks, 7 (1977) pp. 25–35.
[77] J.D. Thompson, D.G. Higgins, and T.J. Gibson. CLUSTAL W: improving the sensitivity
of progressive multiple sequence alignment through sequence weighting, position-specific
gap penalties and weight matrix choice. Nucleoc Acids Res., 22, (1994) pp. 4673–4680.
[78] K.-H. Tsai and D.T. Lee. k-Best Cuts for Circular-Arc Graphs. Algorithmica, 18(2)
(1997) pp. 198–216.
[79] P. Uetz et al. A comprehensive analysis of protein-protein interactions in Saccharomyces
cerevisiae. Nature, 403, (2000) pp. 623–627.
[80] I. Xenarious, L. Salw′ınski, X.J. Duan, P. Higney, S.M. Kim, and D. Eisenberg. DIP,
the database of interacting proteins: a research tool for studying cellular networks of
protein interactions. Nucleoc Acids Res., 30, (2002) pp. 303–305.
[81] G. Xu, L. Kang, E. Shan, and M. Zhao. Power domination in block graphs. Theoret.
Comput. Science, 359 (2006) pp. 299–305.
[82] M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM J. Appl. Math.,
38 (1980) pp. 364–372.
[83] H. Yu, N.M. Luscombe, H.X. Lu, X. Zhu, Y. Xia, J.D. Han, N. Bertin, S. Chung,
M. Vidal, and M. Gerstein. Annotation transfer between genomes: protein protein
interologs and protein DNA regulogs. Genome Res., 14, (2004) pp. 1107–1118.
[84] M. Zhao, L. Kang, and G.J. Chang. Power domination in graphs. Discrete Math.,
306(15) (2006) pp. 1812–1816.