Show simple item record

dc.contributor.authorSamad, Abdul
dc.description.abstractMany intractable problems on graphs are polynomial time solvable when the graphs have bounded treewidth. An important class of the graphs with bounded treewidth is called k-trees, which are formed by starting with a k-clique and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that form a new clique. Finding spanning k-trees has applications in networks where it was first studied in networks, and was later shown to be NP-Complete even for k =2. Biomolecule (protein, RNA) structure prediction is a grand challenge which leads to many computation methods in bioinformatics. We model the biomolecular structure prediction problem as finding the maximum spanning k-tree on the backbone graphs, where the backbone graphs are characterized by a linear sequence of the vertices. However, most of the traditional methods are not powerful to search through the huge conformation space. This implies a strong demand for more efficient models. We prove that the problem is W[1]-hard for the objective function defined on the cliques of the input graph. For solving the problem, we show that the problem can be solved in time O(k.(n)^{k+1}(k+1)^{k+2}) for every given k and we give evidence that our algorithm is very likely to be optimal.Our algorithm also works for different objective function defined over the cliques of the k-tree, which enables pertinent characterizations of real world problems.
dc.subjectRNA Structure Prediction, K-tree, Tree Decoposition, Dynamic Programming
dc.titleFinding optimal spanning k-trees in backbone graphs
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorLiming Cai
dc.description.committeeLiming Cai
dc.description.committeeRobert Robinson
dc.description.committeeRussell Malmberg

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record