New algorithmic approaches to protein spot detection and pattern matching in two-dimensional electrophoresis gel databases

Protein spot identification in two-dimensional electrophoresis gels can be supported by the comparison of gel images accessible in different World Wid e Web two-dimensional electrophoresis (2-DE) gel protein databases. The com parison may be performed either by visual cross-matching between gel images or by automatic recognition of similar protein spot patterns. A prerequisi te for the automatic point pattern matching approach is the detection of pr otein spots yielding the x(s),y(s) coordinates and integrated spot intensit ies i(s). For this purpose an algorithm is developed based on a combination of hierarchical watershed transformation and feature extraction methods. T his approach reduces the strong over-segmentation of spot regions normally produced by watershed transformation. Measures for the ellipticity and curv ature are determined as features of spot regions. The resulting spot lists containing x(s),y(s),i(s)triplets are calculated for a source as well as fo r a target gel image accessible in 2-DE gel protein databases. After spot d etection a matching procedure is applied. Both the matching of a local patt ern vs, a full 2-DE gel image and the global matching between full images a re discussed. Preset slope and length tolerances of pattern edges serve as matching criteria. The local matching algorithm relies on a data structure derived from the incremental Delaunay triangulation of a point set and a tw o-step hashing technique. For the incremental construction of triangles the spot intensities are considered in decreasing order. The algorithm needs n either landmarks nor an a priori image alignment. A graphical user interfac e for spot detection and gel matching is written in the Java programming la nguage for the Internet. The software package called CAROL (http://gelmatch ing.inf.fu-berlin.de) is realized in a client-server architecture.