|
|
|
HomeResearchPublicationsProjects |
Zhang’s
Research
I
am interested in theoretical computer science and its applications. I believe
breakthroughs in theoretical computer science have the potential to affect
all of computer science radically. Algorithms for the Multiple
Sequence Alignment Problem Multiple Sequence Alignment (MSA) is the problem of
finding as many common features as possible among a sequence of DNA or
protein sequences taken from a family of species. MSA is one of the most
fundamental computation problems in molecular biology/bioinformatics that
many biological modeling methods depend on, including phylogenetic trees,
profiles and structure prediction. A fast and accurate computer algorithm for
MSA will greatly benefit and boost the advancement of study in these methods.
However, the MSA problem in its general form has been shown to be NP-hard
[1], indicating that general efficient computer algorithms for this problem
are very unlikely to exist. Thus researchers have been trying to develop
either approximation algorithms or ad hoc heuristic algorithms for MSA that
work well for a particular setting in practice. For example, Gusfield [2]
devised an algorithm with approximation ratio 2 using the sum-of-pairs
criteria to evaluate the goodness of an alignment. Both the Long Run
algorithms by Jiang and Li [2] and the Expansion algorithm by Bonizzoni et
al. [3] can be also applied to the MSA problem with guaranteed approximation
ratios. On the other hand, many heuristic algorithms have been developed to
work for a special set of data. Notredame [4] provides a recent survey. more Algorithms for the Subgraph
Isomorphism Problem With the widespread use of the graph data structure,
finding an efficient algorithm for subgraph isomorphism, i.e., common
subgraphs of two given graphs, is of utmost importance in many areas of
science and engineering such as in pattern recognition, image and video
analysis, bio- and chemo-informatics, etc. to name a few. Yet finding an efficient
algorithm is a very hard problem because of its NP-completeness. The best
algorithms so far seem to be targeted to a reduced set of problems or provide
approximate solutions and they perform poorly for general problems. In this
project we will try a different approach than those mentioned early for
solving this problem. We propose to employ a dovetailing technique in which
multiple algorithms will be interleaved and run so that the fastest one for
the given input will find a solution within the shortest time. Mr. Nazul Grimaldo, graduate student in the CIS
department has been working on this problem under the supervision of Dr. Liyu
Zhang. The above description is essentially Nazul’s thesis proposal
abstract. We need an undergraduate student to help with developing a GUI
and/or a web interface for the implemented algorithms, as well as to help
with improving the performance of our proposed algorithms for the subgraph
isomorphism problem. Depending on his/her interest, the participating senior
student may involve in either or both aspects of the project, and will work
with both the instructor and the graduate student. Disjoint NP-Pairs A disjoint NP-pair is a pair of disjoint, nonempty sets
in NP. The study of disjoint NP-pairs is motivated by its connections to
secure public-key cryptosystems and to propositional proof complexity. The
latter subject is concerned with the complexity of proof systems for
propositional logic, which itself is related to the problem of whether NP
equals coNP. In a reasonable formulation of public-key cryptosystems, the
problem of cracking public-key cryptosystems is equivalent to separating
certain disjoint NP-pairs. For this reason, answers to questions about the
existence of NP-hard or P-inseparable disjoint NP-pairs informs us about the
question of whether secure public-key cryptosystems exist or whether
public-key cryptosystems can be NP hard to crack. more Structural Properties of
Complete Sets One
basic problem in computational complexity is what structural properties
complete sets of different complexity classes have. For example, are all
NP-complete sets dense, meaning that they have exponentially many strings per
length? It is important to study such computational structure of complete
sets, because they, by reductions of all the sets in the class to the
complete sets, represent all of the structure that a class might have. For
this reason, the study of structural properties of complete sets gave us a
better understanding of the computational power of various complexity
classes, and also might lead to proofs of separation results in complexity
theory. more |
|
|
I
would certainly like to continue my research in the area of computational
complexity, specifically on disjoint NP-pairs and structural properties of
complete sets. I am also interested in applications of theoretical computer
science. Computational complexity has close relations with areas such as
cryptography or computer security where tools and concepts of computational
complexity can and indeed need to be applied. I would like to explore these
areas and will look to get applicable results by exploiting ideas and
solutions from the computational complexity sector. Another area I would like
to explore as part of my future research is the design and analysis of
algorithms. more Copyright © 2007 Liyu Zhang. Design by Zhen Li. Last updated: 8/25/2023
3:07:46 PM |
