| Born: 1946, Germany |
Academic Qualifications:Ph.D. 1989, Tel Aviv University
Professor
|
Academic Positions:
|
Research Interests:
For more details please see my webpage http://www.cs.bgu.ac.il/~klara
Kedem's research is in computational geometry with applications to robotics, computer vision and bio-information. She is known for devising the minimum Hausdorff distance for shape matching, a robust method which has had a strong impact and is still being investigated by followers. This metric is being developed now for very fast implementation on GPU (graphics proccessing unit).
She is working on historical document analysis, from binarization to automatic character recognition for ancient degraded documents and for palimpsests.
She has looked into shape comparison problems in life-science disciplines and their applications. In computational molecular biology she came come up with a new metric, the URMS, to measure substructure resemblance between proteins. This measure has been further applied to the analysis of molecular
dynamics, and to her work on structural consensus and multiple
structural alignment for proteins.
Kedem has applied string matching algorithms to protein shape
comparison, and to RNA motif search. She continues her research in RNA structural motif search by converting the secondary structure of the motif to a compressed tree representation and applying subtree homeomorphism for the search. Sequence information is also taken into account in this work. Her consensus shape for protein families is now being applied to
finding protein interaction sites. |
Research Projects:
1. Reconstructing degraded documents
2. Segmentation and texture analysis
3. Theoretical and practical geometric pattern matching algorithms
4. Augmented Reality
5. Curve registration by using projective invariants
6. MicroRNA target prediction
7. Building a library of protein surface patches |
|
Abstracts of Current Research:- Fast Detection of Common Geometric Substructure in Proteins: We consider the problem of identifying common three-dimensionalsubstructures between proteins. Our method is based on comparing theshape of the alpha-carbon backbone structures of the proteins inorder to find 3D rigid motions that bring portions of the geometricstructures into correspondence. We propose a geometric representationof protein backbone chains that is compact yet allows for similaritymeasures that are robust against noise and outliers. We represent thestructure of the backbone as a sequence of unit vectors, defined byeach adjacent pair of alpha-carbons; we then define a measure ofthe similarity of two protein structures based on the RMS (root meansquared) distance between corresponding orientation vectors in the twoproteins.Our measure has several advantages over standard position-based RMSmeasures that are commonly used for comparing protein shapes. Inparticular, the measure behaves well for comparing substructures,because unlike position-based measures the nonmatching portions of thestructure do not dominate the measure. At the same time, it avoidsthe quadratic space and computational difficulties associated with theuse of distance matrices and contact maps. We show applications ofour approach to detecting common contiguous substructures in pairs ofproteins, as well as the more difficult problem of identifying commonprotein domains (i.e., larger substructures that are not necessarilycontiguous along the protein chain).
- Improved Algorithms for Placing Undesirable Facilities: We improve a number of existing algorithms fordetermining the location of one or more undesirablefacilities amidst a set P of n demand points, and under variousconstraints and distance metrics. The demand pointsreside within some given bounded region.Applying concepts and techniques from Computational Geometrywe provide efficient algorithms for the following problems:1. Brimberg Mehrez `94: Locate k undesirable facilities under the constraintsthat the smallest distance between each demand point and the facilities isgreater than a given r , and the distance between two facilities is greaterthan some given d.Under (rectangular) metrics (e.g., L_1) we present efficient algorithmsfor any k , and for the Euclidean distance we can locate efficiently twosuch facilities.2. Brimberg Wesolowsky `95: Locate one obnoxious facilityamidst n weighted demand points, such that the rectangular distance betweeneach point and the facility is larger than a corresponding constantand the sum of the weighted distances between the demand points and thefacility is minimized.3. Drezner Wesolowsky `94: Given a rectangle (or a circle)find a position to locate them so as to minimize the sumof weights of the points they contain.
- Optimal Facility Location under Various Distance Functions: We present efficient algorithms for two problemsof facility location.In both problems we want to determine the location of a single facilitywith respect to n given sites.In the first we seek a location that maximizesa weighted distance function between the facility and the sites,and in the second we find a location that minimizesthe sum (or sum of the squares)of the distances of at least k of the sites from the facility.
|
Publications:- Kedem, K. & Chew, L.P.. Getting around a lower bound for the minimum Hausdorff distance. Computational Geometry: Theory and Applications 10: 197--202 (1998)
- Kedem, K. & Segal, M.. Enclosing k points in the smallest enclosing axis parallel rectangle. Information Processing Letters. 65: 95--99 (1998)
- Kedem, K., Katz, M. & Segal, M.. Constrained Square Center Problems. Lecture Notes in Computer Science,Springer-Verlag 1432: 95-106 (1998)
- Kedem, K.. Geometric pattern matching under euclidean motion 7: 113-124 (1997)
- Kedem, K.. Geometric Applications Of Posets. Lecture Notes in Computer Science,Springer-Verlag 1272: 402-415 (1997)
|
|
|
|
| Keywords:Computational Geometry, Hausdorff Distance, Computer Vision, Bio-information. |
|
Phones:
- Phone: 972-3-6478280
- Fax: 972-8-6477650
- Mobile: 054-8100551
|
|
| |