Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Home Page for Hsin-Yi (Cindy) Yeh | Parasol Laboratory

Picture Hsin-Yi (Cindy) Yeh
PhD Student
Algorithms & Applications Group

Parasol Laboratory url: http://parasol.tamu.edu/~hyeh/
Department of Computer Science and Engineering email:
Texas A&M University office: 407E HRBB
College Station, TX 77843-3112 tel: (979) 847-8835
USA fax: (979) 458-0718

I am a Ph.D. student in the Department of Computer Science and Engineering at Texas A&M University. I received a B.S. in Department of Computer Science and Information Engineering from National Taiwan University in June 2008. I currently work with Professor Nancy Amato and do research in the field of computational biology. What we study is the protein folding process by randomized motion planning algorithms.

My research focuses on a uniform sampling framework for Probabilistic Roadmap method. The framework is able to sample uniformly over some specific target surfaces in the environment by some test of surface membership. Knowing that the distribution is uniform ensures that the surface is well represented. Two instances of the framework are developed: UOBPRM and UMAPRM. UOBPRM samples obstacle surfaces by simply watching validity changes between neighboring configurations on a random line segment. UMAPRM samples the medial axis by checking witness points changes between consecutive configurations on a random line segment. The uniform sampling framework generates uniformly distributed configurations in the targeted surfaces by checking the intersection between the fixed length line segment and the targeted surfaces. Thus, the performance of the uniform sampling framework is not affected when the surface area is unchanged, e.g., UOBPRM is unaffected when the narrow passage width decreases and UMAPRM's performance is stable with respect to the changes in the surrounding obstacle volume when the surface area of the medial axis remains the same. We also evaluate both UOBPRM and UMAPRM in some difficult motion planning problems and find that they are more efficiently than other sampling methods.


My research interests are Computational Biology and Motion Planning.

CV     Research Statement


Computational Biology:

Protein Folding
There are many biochemical processes closely related to the protein folding. Therefore, the study of protein folding can give us a deeper understanding of those complex biochemical processes, such as protein-ligand binding, enzyme reactions, and the diseases caused by misfolding like Cystic fibrosis and Marfan syndrome. Since it is quite difficult to experimentally monitor these motions, simulations have become essential to their study. The purpose of this work is to study how protein folds and its motions by PRM (probabilistic roadmap method) framework.
Decoy Database Improvement
Predicting protein structures and simulating protein folding are two of the most important problems in computational biology today. Simulation methods rely on a scoring function to distinguish the native structure (the most energetically stable) from non-native structures. Decoy databases are collections of non-native structures used to test and verify these functions. We present a method to evaluate and improve the quality of decoy databases by adding novel structures and removing redundant structures. We test our approach on 20 different decoy databases of varying size and type and show significant improvement across a variety of metrics. We also test our improved databases on two popular modern scoring functions and show that for most cases they contain a greater or equal number of native-like structures than the original databases, thereby producing a more rigorous database for testing scoring functions.

Motion Planning:
Uniform Sampling Framework for PRMs
We introduce a strategy to uniformly sample any surfaces in C-space. Our uniform sampling framework first uniformly distributes a set of fixed-length line segments in C-space. Intermediate configurations are tested at a fixed resolution for membership to the target surface. Those that belong to the target surface are retained in the roadmap. Intuitively, since the line segments are uniformly distributed, the points retained from the segments are also uniformly distributed.
Uniform OBPRM
We present a new sampling method for motion planning which can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. In our approach, roadmap nodes are generated from the intersections between obstacles and a set of uniformly distributed segments in the environment. The results show that UOBPRM yields samples that are more uniformly distributed than previous obstacle-based methods such as OBPRM, Gaussian sampling, and Bridge test sampling. UOBPRM has the lowest percentage difference to the ideal case and also uses the fewest nodes and edges to solve a challenging motion planning problem with varying narrow passages.
Uniform MAPRM
We introduce a novel planning variant, Uniform Medial Axis Probabilistic Roadmap (UMAPRM) that generates samples uniformly on the medial axis of the free portion of C-space. UMAPRM generates samples by checking the intersections between the fixed length line segment that are uniformly distributed in the space and the medial axis. Our results show that UMAPRM's distribution of samples along the medial axis is not only uniform buy also preferable to other medial axis samplers in certain planning problems. We demonstrate that UMAPRM has negligible computational overhead over other sampling techniques and can solve problems the others could not. We also show that UMAPRM successfully generates higher clearance paths in the examples.


Uniform Sampling Framework for Sampling Based Motion Planning and Its Applications to Robotics and Protein Ligand Binding, Hsin-Yi (Cindy) Yeh, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, May 2016.
Ph.D. Thesis(pdf, abstract)

Decoy Database Improvement for Protein Folding, Hsin-Yi (Cindy) Yeh, Aaron Lindsey, Chih-Peng Wu, Shawna Thomas, Nancy M. Amato, Journal of Computational Biology, 22(9):823 - 836, Sep 2015.
Journal(pdf, abstract)

Improving Decoy Databases for Protein Folding Algorithms, Aaron Lindsey, Hsin-Yi (Cindy) Yeh, Chih-Peng Wu, Shawna Thomas, Nancy M. Amato, In ACM Conf. on Bioinformatics, Comput. Biology and Health Informatics on Computational Structural Bioinformatics Wkshp., pp. 717 - 724, Newport Beach, CA, Sep 2014.
Proceedings(ps, pdf, abstract)

Improving Decoy Databases for Protein Folding Algorithms , Aaron Lindsey, Hsin-Yi (Cindy) Yeh, Chih-Peng Wu, Shawna Thomas, Nancy M. Amato, In Proc.of 2014 RSS Wkshp. on Robotics Methods for Structural and Dynamic Modeling of Molecular Systems, Berkeley, CA, Jul 2014.
Proceedings(ps, pdf, abstract)

UMAPRM: Uniformly Sampling the Medial Axis, Hsin-Yi (Cindy) Yeh, Jory Denny, Aaron Lindsey, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5798 - 5803, Hong Kong, China, Jun 2014.
Proceedings(ps, pdf, abstract)

Rigidity Analysis for Protein Motion and Folding Core Identification, Shawna Thomas, Lydia Tapia, Chinwe Ekenna, Hsin-Yi (Cindy) Yeh, Nancy M. Amato, In Proc. of 2013 AAAI Wkshp. on Art. Int. and Robot. Meth. in Comp. Bio., Bellevue, WA, Jul 2013.
Proceedings(pdf, abstract)

Nearly Uniform Sampling on Surfaces with Applications to Motion Planning, Mukulika Ghosh, Cindy (Hsin-Yi) Yeh, Shawna Thomas, Nancy M. Amato, Technical Report, TR13-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Apr 2013.
Technical Report(pdf, abstract)

UOBPRM: A Uniformly Distributed Obstacle-Based PRM, Cindy (Hsin-Yi) Yeh, Shawna Thomas, David Eppstein, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 2655-2662, Vilamoura, Algarve, Portugal, Oct 2012.
Proceedings(ps, pdf, ppt, abstract)