NAMIC Wiki - User contributions [en]

Projects:NonParametricClustering

2008-12-09T23:39:40Z

Xavier: /* Results */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Non Parametric Clustering for Biomolecular Structural Analysis =

High accuracy imaging and image processing techniques allow for collecting structural information of biomolecules with atomistic accuracy. Direct interpretation of the dynamics and the functionality of these structures with physical models, is yet to be developed. Clustering of molecular conformations into classes seems to be the first stage in recovering the formation and the functionality of these molecules. The lack of prior knowledge such as number and shape of the clusters in the data space can be resolved most efficiently by using non parametric clustering methods. We are currently developing an application based on a Potts model method that was proposed by Blatt Wiseman and Domany to deal with the structure of the biomolecules.

= Description =

The purpose of this work is to adapt a non-parametric clustering algorithm for data mining of RNA structures. One of the main challenges of bioinformatics is to develop data mining tools for the available RNA structures from data banks in order to establish structure-function relationship. To do so a coherent objective classification method is required. To test such methods we are currently analyzing the conformational data space of single and double nucleotides only (Fig 1).

{|
|+ '''Fig 1. RNA Conformation Representations'''
|valign="top"|[[Image:RNABackbone.JPG|thumb|250px|RNA backbone with six torsion angles labeled on the central bond of the four atoms defining each dihedral. The two alternative ways of parsing out a repeat are indicated: A traditional nucleotide residue goes from phosphate to phosphate, whereas an RNA suite, which is more appropriate for local geometry analysis, goes from sugar to sugar (or base to base).]]
|valign="top"|[[Image:BasePair3DModel.JPG|thumb|250px|A typical base base interaction is the base pairs interaction where the interacting bases are on the same plane.]]
|}

== Clustering method ==

Our method of choice for the clustering of the data space is based on a physical Potts model. The N points of our dataset are referred as magnetic sites. Each site is assigned a Potts spin. Spin values are taken from a set of q distinct integers. An interaction term that is proportional to the distance between nearest neighbor’s data points is added to the model. The spin configuration of our model is dependent on a parameter T that physically corresponds to a temperature. Such Potts systems are known to form a phase with islands of similar Potts state (similar magnetic state). Revealing the clusters in the data space is converted into Monte Carlo search for the magnetic islands in the equivalent physical model. While this method is slow comparing to other non parametric hierarchical methods, it is by far superior in robustness and its classification is more coherent due to its physical interpretation. We compare our results to linkage-based clustering methods, which are popular non-parametric clustering methods.

== Results ==

=== Single Nucleotide ===

The single nucleotide conformation is the basic structural unit of the RNA shape. The flexibility of a residue stems from the modes of motion of its backbone, which are restricted to 6 rotations. The backbone conformation distribution is strongly non-homogeneous and we then operate clustering in this 6-dimensional torsional space.

Comparison of the resulting clustering (3D projection) with previous prior knowledge reveals an excellent match (Fig 2).

{|
|+ '''Fig 2. Single Nucleotide Clustering'''
|valign="top"|[[Image:SingleNucleotideBins.JPG|thumb|400px|3D projection of the clustering for the qualitattive observations.]]
|valign="top"|[[Image:SingleNucleotidePotts.JPG|thumb|400px|3D projection of the clustering for the classification with the proposed clustering method.]]
|}

Also, we have compare our method to linkage-based clustering methods. These hierarchical methods necessitate more prior knowledge in order to select an optimal clustering configuration within the iterative data decomposition into clusters. Final clustering seems to be much easier to obtain and interpret with the Potts proposed model.

=== Base Pair ===

Interactions within the RNA strand can bring residues that are initially far apart in the sequence into close proximity. Studying interacting base pair geometries can shed light on the folding process and the functionality of an RNA molecule. The Potts based clustering give the results presented in (Fig 3). Our analysis shows that we have been able to reconstruct with high fidelity -and somehow complete- the base pair classification one can find in data banks.

{|
|+ '''Fig 3. Base Pair Clustering'''
|valign="top"|[[Image:BasePairAllPoints.JPG|thumb|400px|2D projection of the data points to cluster for the base pair geometry case. The coordinates of the projection are theta and omega.]]
|valign="top"|[[Image:BasePairClustersPotts.JPG|thumb|400px|Proposed clustering: the first 8 clusters correspond to the classification in the literature (Data Banks).]]
|}

== Project status ==

Thus far we have applied the method to classify single nucleotide and base pair conformations. At the current stage we are developing classification nomenclature for base stacking, an interaction that have not been given an adequate physical model nor been classified.

= Project aim =

A variant of the Potts model classification can be used to find clustering in network of interactions between molecules. We plan to use the Potts model with results from projects of polymers adsorption that we are currently working on to develop model for docking interactions between polymers and between polymers and metal surfaces.

= Key Investigators =

* Georgia Tech: E. Hershkovits, X. Le Faucheur, R. Tannenbaum and A. Tannenbaum

= Publications =
''In Print''

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3ANonParametricClustering&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

''In press''
* X. Le Faucheur, E. Hershkovits, R. Tannenbaum and A. Tannenbaum. Non-Parametric Clustering for studying RNA conformation. Publication in submission.

Projects:NonParametricClustering

2008-12-09T23:38:52Z

Xavier: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Non Parametric Clustering for Biomolecular Structural Analysis =

High accuracy imaging and image processing techniques allow for collecting structural information of biomolecules with atomistic accuracy. Direct interpretation of the dynamics and the functionality of these structures with physical models, is yet to be developed. Clustering of molecular conformations into classes seems to be the first stage in recovering the formation and the functionality of these molecules. The lack of prior knowledge such as number and shape of the clusters in the data space can be resolved most efficiently by using non parametric clustering methods. We are currently developing an application based on a Potts model method that was proposed by Blatt Wiseman and Domany to deal with the structure of the biomolecules.

= Description =

The purpose of this work is to adapt a non-parametric clustering algorithm for data mining of RNA structures. One of the main challenges of bioinformatics is to develop data mining tools for the available RNA structures from data banks in order to establish structure-function relationship. To do so a coherent objective classification method is required. To test such methods we are currently analyzing the conformational data space of single and double nucleotides only (Fig 1).

{|
|+ '''Fig 1. RNA Conformation Representations'''
|valign="top"|[[Image:RNABackbone.JPG|thumb|250px|RNA backbone with six torsion angles labeled on the central bond of the four atoms defining each dihedral. The two alternative ways of parsing out a repeat are indicated: A traditional nucleotide residue goes from phosphate to phosphate, whereas an RNA suite, which is more appropriate for local geometry analysis, goes from sugar to sugar (or base to base).]]
|valign="top"|[[Image:BasePair3DModel.JPG|thumb|250px|A typical base base interaction is the base pairs interaction where the interacting bases are on the same plane.]]
|}

== Clustering method ==

Our method of choice for the clustering of the data space is based on a physical Potts model. The N points of our dataset are referred as magnetic sites. Each site is assigned a Potts spin. Spin values are taken from a set of q distinct integers. An interaction term that is proportional to the distance between nearest neighbor’s data points is added to the model. The spin configuration of our model is dependent on a parameter T that physically corresponds to a temperature. Such Potts systems are known to form a phase with islands of similar Potts state (similar magnetic state). Revealing the clusters in the data space is converted into Monte Carlo search for the magnetic islands in the equivalent physical model. While this method is slow comparing to other non parametric hierarchical methods, it is by far superior in robustness and its classification is more coherent due to its physical interpretation. We compare our results to linkage-based clustering methods, which are popular non-parametric clustering methods.

== Results ==

=== Single Nucleotide ===

The single nucleotide conformation is the basic structural unit of the RNA shape. The flexibility of a residue stems from the modes of motion of its backbone, which are restricted to 6 rotations. The backbone conformation distribution is strongly non-homogeneous and we then operate clustering in this 6-dimensional torsional space.

Comparison of the resulting clustering (3D projection) with previous prior knowledge reveals an excellent match (Fig 2).

{|
|+ '''Fig 2. Single Nucleotide Clustering'''
|valign="top"|[[Image:SingleNucleotideBins.JPG|thumb|400px|3D projection of the clustering for the qualitattive observations.]]
|valign="top"|[[Image:SingleNucleotidePotts.JPG|thumb|400px|3D projection of the clustering for the classification with the new clustering method.]]
|}

Also, we have compare our method to linkage-based clustering methods. These hierarchical methods necessitate more prior knowledge in order to select an optimal clustering configuration within the iterative data decomposition into clusters. Final clustering seems to be much easier to obtain and interpret with the Potts proposed model.

=== Base Pair ===

Interactions within the RNA strand can bring residues that are initially far apart in the sequence into close proximity. Studying interacting base pair geometries can shed light on the folding process and the functionality of an RNA molecule. The Potts based clustering give the results presented in (Fig 3). Our analysis shows that we have been able to reconstruct with high fidelity -and somehow complete- the base pair classification one can find in data banks.

{|
|+ '''Fig 3. Base Pair Clustering'''
|valign="top"|[[Image:BasePairAllPoints.JPG|thumb|400px|2D projection of the data points to cluster for the base pair geometry case. The coordinates of the projection are theta and omega.]]
|valign="top"|[[Image:BasePairClustersPotts.JPG|thumb|400px|Proposed clustering: the first 8 clusters correspond to the classification in the literature (Data Banks).]]
|}

== Project status ==

Thus far we have applied the method to classify single nucleotide and base pair conformations. At the current stage we are developing classification nomenclature for base stacking, an interaction that have not been given an adequate physical model nor been classified.

= Project aim =

A variant of the Potts model classification can be used to find clustering in network of interactions between molecules. We plan to use the Potts model with results from projects of polymers adsorption that we are currently working on to develop model for docking interactions between polymers and between polymers and metal surfaces.

= Key Investigators =

* Georgia Tech: E. Hershkovits, X. Le Faucheur, R. Tannenbaum and A. Tannenbaum

= Publications =
''In Print''

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3ANonParametricClustering&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

''In press''
* X. Le Faucheur, E. Hershkovits, R. Tannenbaum and A. Tannenbaum. Non-Parametric Clustering for studying RNA conformation. Publication in submission.

File:BasePairClustersPotts.JPG

2008-12-09T22:55:02Z

Xavier:

File:BasePairAllPoints.JPG

2008-12-09T22:54:47Z

Xavier:

Projects:NonParametricClustering

2008-12-09T22:54:17Z

Xavier: /* Results */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Non Parametric Clustering for Biomolecular Structural Analysis =

High accuracy imaging and image processing techniques allow for collecting structural information of biomolecules with atomistic accuracy. Direct interpretation of the dynamics and the functionality of these structures with physical models, is yet to be developed. Clustering of molecular conformations into classes seems to be the first stage in recovering the formation and the functionality of these molecules. The lack of prior knowledge such as number and shape of the clusters in the data space can be resolved most efficiently by using non parametric clustering methods. We are currently developing an application based on a Potts model method that was proposed by Blatt Wiseman and Domany to deal with the structure of the biomolecules.

= Description =

The purpose of this work is to adapt a non-parametric clustering algorithm for data mining of RNA structures. One of the main challenges of bioinformatics is to develop data mining tools for the available RNA structures from data banks in order to establish structure-function relationship. To do so a coherent objective classification method is required. To test such methods we are currently analyzing the conformational data space of single and double nucleotides only (Fig 1).

{|
|+ '''Fig 1. RNA Conformation Representations'''
|valign="top"|[[Image:RNABackbone.JPG|thumb|250px|RNA backbone with six torsion angles labeled on the central bond of the four atoms defining each dihedral. The two alternative ways of parsing out a repeat are indicated: A traditional nucleotide residue goes from phosphate to phosphate, whereas an RNA suite, which is more appropriate for local geometry analysis, goes from sugar to sugar (or base to base).]]
|valign="top"|[[Image:BasePair3DModel.JPG|thumb|250px|A typical base base interaction is the base pairs interaction where the interacting bases are on the same plane.]]
|}

== Clustering method ==

Our method of choice for the clustering of the data space is based on a physical Potts model. The N points of our dataset are referred as magnetic sites. Each site is assigned a Potts spin. Spin values are taken from a set of q distinct integers. An interaction term that is proportional to the distance between nearest neighbor’s data points is added to the model. The spin configuration of our model is dependent on a parameter T that physically corresponds to a temperature. Such Potts systems are known to form a phase with islands of similar Potts state (similar magnetic state). Revealing the clusters in the data space is converted into Monte Carlo search for the magnetic islands in the equivalent physical model. While this method is slow comparing to other non parametric hierarchical methods, it is by far superior in robustness and its classification is more coherent due to its physical interpretation. We compare our results to linkage-based clustering methods, which are popular non-parametric clustering methods.

== Results ==

=== Single Nucleotide ===

The single nucleotide conformation is the basic structural unit of the RNA shape. The flexibility of a residue stems from the modes of motion of its backbone, which are restricted to 6 rotations. The backbone conformation distribution is strongly non-homogeneous and we then operate clustering in this 6-dimensional torsional space.

Comparison of the resulting clustering (3D projection) with previous prior knowledge reveals an excellent match (Fig 2).

{|
|+ '''Fig 2. Single Nucleotide Representations'''
|valign="top"|[[Image:SingleNucleotideBins.JPG|thumb|400px|3D projection of the clustering for the qualitattive observations.]]
|valign="top"|[[Image:SingleNucleotidePotts.JPG|thumb|400px|3D projection of the clustering for the classification with the new clustering method.]]
|}

=== Base Pair ===

Interactions within the RNA strand can bring residues that are initially far apart in the sequence into close proximity. Studying interacting base pair geometries can shed light on the folding process and the functionality of an RNA molecule. The Potts based clustering give the results presented in (Fig 3). Our analysis shows that we have been able to reconstruct with high fidelity -and somehow complete- the base pair classification one can find in data banks.

{|
|+ '''Fig 3. Nucleotide Doublet Representations'''
|valign="top"|[[Image:BasePairConformation.JPG|thumb|250px|2D projection of the clustering for the base pair geometry case. The coordinates of the projection are theta and omega. (a) All the data points before clustering. (b) After clustering with the algorithm the first seven clusters that correspond to the classification in the literature.]]
|}

''Project status''

Thus far we have applied the method to classify single nucleotide conformation. Comparison of the resulting clustering with previous prior knowledge based K mean algorithm reveals an excellent match (Fig 2). We have also reconstructed with high fidelity the consensus base pair classification (Fig 3). At the current stage we are developing classification nomenclature for base stacking, an interaction that have not been given an adequate physical model nor been classified.

''Project aim''

A variant of the Potts model classification can be used to find clustering in network of interactions between molecules. We plan to use the Potts model with results from projects of polymers adsorption that we are currently working on to develop model for docking interactions between polymers and of polymer with surfaces.

= Key Investigators =

* Georgia Tech: E. Hershkovits, X. Le Faucheur, R. Tannenbaum and A. Tannenbaum

= Publications =
''In Print''

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3ANonParametricClustering&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

''In press''
* X. Le Faucheur, E. Hershkovits, R. Tannenbaum and A. Tannenbaum. Non-Parametric Clustering for studying RNA conformation. Publication in submission.

Projects:NonParametricClustering

2008-12-09T22:41:20Z

Xavier: /* Results */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Non Parametric Clustering for Biomolecular Structural Analysis =

High accuracy imaging and image processing techniques allow for collecting structural information of biomolecules with atomistic accuracy. Direct interpretation of the dynamics and the functionality of these structures with physical models, is yet to be developed. Clustering of molecular conformations into classes seems to be the first stage in recovering the formation and the functionality of these molecules. The lack of prior knowledge such as number and shape of the clusters in the data space can be resolved most efficiently by using non parametric clustering methods. We are currently developing an application based on a Potts model method that was proposed by Blatt Wiseman and Domany to deal with the structure of the biomolecules.

= Description =

The purpose of this work is to adapt a non-parametric clustering algorithm for data mining of RNA structures. One of the main challenges of bioinformatics is to develop data mining tools for the available RNA structures from data banks in order to establish structure-function relationship. To do so a coherent objective classification method is required. To test such methods we are currently analyzing the conformational data space of single and double nucleotides only (Fig 1).

{|
|+ '''Fig 1. RNA Conformation Representations'''
|valign="top"|[[Image:RNABackbone.JPG|thumb|250px|RNA backbone with six torsion angles labeled on the central bond of the four atoms defining each dihedral. The two alternative ways of parsing out a repeat are indicated: A traditional nucleotide residue goes from phosphate to phosphate, whereas an RNA suite, which is more appropriate for local geometry analysis, goes from sugar to sugar (or base to base).]]
|valign="top"|[[Image:BasePair3DModel.JPG|thumb|250px|A typical base base interaction is the base pairs interaction where the interacting bases are on the same plane.]]
|}

== Clustering method ==

Our method of choice for the clustering of the data space is based on a physical Potts model. The N points of our dataset are referred as magnetic sites. Each site is assigned a Potts spin. Spin values are taken from a set of q distinct integers. An interaction term that is proportional to the distance between nearest neighbor’s data points is added to the model. The spin configuration of our model is dependent on a parameter T that physically corresponds to a temperature. Such Potts systems are known to form a phase with islands of similar Potts state (similar magnetic state). Revealing the clusters in the data space is converted into Monte Carlo search for the magnetic islands in the equivalent physical model. While this method is slow comparing to other non parametric hierarchical methods, it is by far superior in robustness and its classification is more coherent due to its physical interpretation. We compare our results to linkage-based clustering methods, which are popular non-parametric clustering methods.

== Results ==

=== Single Nucleotide ===

The single nucleotide conformation is the basic structural unit of the RNA shape. The flexibility of a residue stems from the modes of motion of its backbone, which are restricted to 6 rotations. The backbone conformation distribution is strongly non-homogeneous and we then operate clustering in this 6-dimensional torsional space.

Comparison of the resulting clustering with previous prior knowledge reveals an excellent match (Fig 2).

{|
|+ '''Fig 2. Single Nucleotide Representations'''
|valign="top"|[[Image:SingleNucleotideBins.JPG|thumb|400px|3D projection of the clustering for the qualitattive observations.]]
|valign="top"|[[Image:SingleNucleotidePotts.JPG|thumb|400px|3D projection of the clustering for the classification with the new clustering method.]]
|}

{|
|+ '''Fig 3. Nucleotide Doublet Representations'''
|valign="top"|[[Image:BasePairConformation.JPG|thumb|250px|2D projection of the clustering for the base pair geometry case. The coordinates of the projection are theta and omega. (a) All the data points before clustering. (b) After clustering with the algorithm the first seven clusters that correspond to the classification in the literature.]]
|}

''Project status''

Thus far we have applied the method to classify single nucleotide conformation. Comparison of the resulting clustering with previous prior knowledge based K mean algorithm reveals an excellent match (Fig 2). We have also reconstructed with high fidelity the consensus base pair classification (Fig 3). At the current stage we are developing classification nomenclature for base stacking, an interaction that have not been given an adequate physical model nor been classified.

''Project aim''

A variant of the Potts model classification can be used to find clustering in network of interactions between molecules. We plan to use the Potts model with results from projects of polymers adsorption that we are currently working on to develop model for docking interactions between polymers and of polymer with surfaces.

= Key Investigators =

* Georgia Tech: E. Hershkovits, X. Le Faucheur, R. Tannenbaum and A. Tannenbaum

= Publications =
''In Print''

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3ANonParametricClustering&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

''In press''
* X. Le Faucheur, E. Hershkovits, R. Tannenbaum and A. Tannenbaum. Non-Parametric Clustering for studying RNA conformation. Publication in submission.

Projects:NonParametricClustering

2008-12-09T22:40:56Z

Xavier: /* Results */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Non Parametric Clustering for Biomolecular Structural Analysis =

High accuracy imaging and image processing techniques allow for collecting structural information of biomolecules with atomistic accuracy. Direct interpretation of the dynamics and the functionality of these structures with physical models, is yet to be developed. Clustering of molecular conformations into classes seems to be the first stage in recovering the formation and the functionality of these molecules. The lack of prior knowledge such as number and shape of the clusters in the data space can be resolved most efficiently by using non parametric clustering methods. We are currently developing an application based on a Potts model method that was proposed by Blatt Wiseman and Domany to deal with the structure of the biomolecules.

= Description =

The purpose of this work is to adapt a non-parametric clustering algorithm for data mining of RNA structures. One of the main challenges of bioinformatics is to develop data mining tools for the available RNA structures from data banks in order to establish structure-function relationship. To do so a coherent objective classification method is required. To test such methods we are currently analyzing the conformational data space of single and double nucleotides only (Fig 1).

{|
|+ '''Fig 1. RNA Conformation Representations'''
|valign="top"|[[Image:RNABackbone.JPG|thumb|250px|RNA backbone with six torsion angles labeled on the central bond of the four atoms defining each dihedral. The two alternative ways of parsing out a repeat are indicated: A traditional nucleotide residue goes from phosphate to phosphate, whereas an RNA suite, which is more appropriate for local geometry analysis, goes from sugar to sugar (or base to base).]]
|valign="top"|[[Image:BasePair3DModel.JPG|thumb|250px|A typical base base interaction is the base pairs interaction where the interacting bases are on the same plane.]]
|}

== Clustering method ==

Our method of choice for the clustering of the data space is based on a physical Potts model. The N points of our dataset are referred as magnetic sites. Each site is assigned a Potts spin. Spin values are taken from a set of q distinct integers. An interaction term that is proportional to the distance between nearest neighbor’s data points is added to the model. The spin configuration of our model is dependent on a parameter T that physically corresponds to a temperature. Such Potts systems are known to form a phase with islands of similar Potts state (similar magnetic state). Revealing the clusters in the data space is converted into Monte Carlo search for the magnetic islands in the equivalent physical model. While this method is slow comparing to other non parametric hierarchical methods, it is by far superior in robustness and its classification is more coherent due to its physical interpretation. We compare our results to linkage-based clustering methods, which are popular non-parametric clustering methods.

== Results ==

=== Single Nucleotide ===

The single nucleotide conformation is the basic structural unit of the RNA shape. The flexibility of a residue stems from the modes of motion of its backbone, which are restricted to 6 rotations. The backbone conformation distribution is strongly non-homogeneous and we then operate clustering in this 6-dimensional torsional space.

Comparison of the resulting clustering with previous prior knowledge reveals an excellent match (Fig 2).

{|
|+ '''Fig 2. Single Nucleotide Representations'''
|valign="top"|[[Image:ASCIIBins.JPG|thumb|400px|3D projection of the clustering for the qualitattive observations.]]
|valign="top"|[[Image:ClusterBins.JPG|thumb|400px|3D projection of the clustering for the classification with the new clustering method.]]
|}

{|
|+ '''Fig 3. Nucleotide Doublet Representations'''
|valign="top"|[[Image:BasePairConformation.JPG|thumb|250px|2D projection of the clustering for the base pair geometry case. The coordinates of the projection are theta and omega. (a) All the data points before clustering. (b) After clustering with the algorithm the first seven clusters that correspond to the classification in the literature.]]
|}

''Project status''

Thus far we have applied the method to classify single nucleotide conformation. Comparison of the resulting clustering with previous prior knowledge based K mean algorithm reveals an excellent match (Fig 2). We have also reconstructed with high fidelity the consensus base pair classification (Fig 3). At the current stage we are developing classification nomenclature for base stacking, an interaction that have not been given an adequate physical model nor been classified.

''Project aim''

A variant of the Potts model classification can be used to find clustering in network of interactions between molecules. We plan to use the Potts model with results from projects of polymers adsorption that we are currently working on to develop model for docking interactions between polymers and of polymer with surfaces.

= Key Investigators =

* Georgia Tech: E. Hershkovits, X. Le Faucheur, R. Tannenbaum and A. Tannenbaum

= Publications =
''In Print''

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3ANonParametricClustering&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

''In press''
* X. Le Faucheur, E. Hershkovits, R. Tannenbaum and A. Tannenbaum. Non-Parametric Clustering for studying RNA conformation. Publication in submission.

File:SingleNucleotidePotts.JPG

2008-12-09T22:39:34Z

Xavier:

File:SingleNucleotideBins.JPG

2008-12-09T22:37:49Z

Xavier:

File:ASCIIBins.JPG

2008-12-09T22:31:39Z

Xavier: uploaded a new version of "Image:ASCIIBins.JPG": Reverted to version as of 19:41, 28 April 2008

2008-04-28T20:05:53Z

Xavier:

Projects:WaveletShrinkage

2008-04-28T20:05:08Z

Projects:OptimalMassTransportRegistration

2008-04-28T19:16:56Z

Xavier:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

The aim of this project to provide a computationaly efficient non-rigid/elastic image registration algorithm based on the Optimal Mass Transport theory. We use the Monge-Kantorovich formulation of the Optimal Mass Transport problem and implement the solution proposed by Haker et al. using multi-resolution and multigrid techniques to speed up the convergence. We also leverage the computation power of general purpose graphics processing units available on standard desktop computing machines to exploit the inherent parallelism in our algorithm.

= Description =

The Optimal Mass Transport problem was first formulated by a Frech engineer Gasper Monge in 1781, and was given a modern formulation in the work of Kantorovich and, therefore, is now known as the Monge-Kantorovich problem. We extend the work by Haker et al. who compute the optimal warp from a first order partial differential equation, an improvement over earlier proposed higher order methods and those based on linear programming. We implement the algorithm using a coarse-to-fine strategy resulting in phenomenol improvement in convergence. The algorithm also involves inverting the Laplacian in each iteration, which we perform using multigrid methods for even faster per iteration computation times. This method has a number of distinguishing characteristics:

# It is a parameter free method.
# It utillizes all of the grayscale data in both images.
# It is symmetrical; the optimal mapping from image A to image B is the inverse of the optimal mapping from B to A.
# No landmarks need to be specified.
# The minimizer of the functional involved is unique; there are no local minimizers.
# The algorithm is designed to take into account changes in densities that result from changes in area or volume.

''Algorithm''

The flowchart of the algorithm is shown in the following figure.

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

 

''Multi-resolution Approach''

Performing image registration using a multi-resolution approach is widely used to improve speed, accuracy and robustness. Registration is first performed at a coarse scale. The spatial mapping determined at coarse scale is then used to initialize registration at the next finer scale. This process is repeated until it reaches the finest scale. Our coarse-to-fine hierarchy comprises of three levels and we use bi-cubic interpolation to interpolate results from coarse to fine grid. This process is depicted in the following figure.
 

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

Below we show the results from registration of two 3D brain MRI datasets. The first data set was pre-operative while the second data set was acquired during surgery (craniotomy). Both were resampled to 256*256*256 for uniform voxel size and the skull was removed. We show the results on an axial and a coronal slice of the 3D brain volumes. The sag and compression areas can easily be seen in the deformed grid shown below. The reults shown are after 3600 iterations, requiring less than 15 minutes of computation time (Dual Xeon 1.6GHz + nVidia GeForce 8800 GX GPU. The optimal computation time was found to occur for a grid size of 128*128*128 where about 1000 iterations execute in less than 15 seconds. This is due to the memory limitations on the graphics card used. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Kilian Pohl, Eldad Haber, Allen Tannenbaum
* BWH: Steven Haker, Ron Kikinis

= Publications =

* T. Rehman and A. Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. SPIE Computation Imaging V, 2007
* T. Rehman, G. Pryor and A. Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. British Machine Vision Conference 2007.
* T. Rehman, G. Pryor, J. Melonakos and A. Tannenbaum. Multiresolution 3D Nonrigid Registration via Optimal Mass Transport. MICCAI workshop on Computational Biomechanics II.
* L. Zhu, Y. Yang, S. Haker and Tannenbaum, ``An image morphing technique based on optimal mass preserving mapping,'' IEEE Trans. Image Processing, volume 16, pp. 1481-1495, 2007.

[[Category:Registration]] [[Category:MRI]]

Projects:WaveletShrinkage

2008-04-28T19:16:29Z

Xavier: New page: Back to NA-MIC Collaborations, Georgia Tech Algorithms __NOTOC__ = Wavelet Shrinkage for Shape Analysis = ...

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

= Wavelet Shrinkage for Shape Analysis =

= Description =

= Key Investigators =

* Georgia Tech: Allen Tannenbaum

= Publications =

''In press''
* Bayesian Spherical Wavelet Shrinkage:Applications to shape analysis, X. Le Faucheur, B. Vidakovic, A. Tannenbaum, Proc. of SPIE Optics East, 2007.

[[Category:Shape Analysis]]

Algorithm:GATech

2008-04-28T19:14:01Z

Xavier:

Back to [[Algorithm:Main|NA-MIC Algorithms]]
__NOTOC__
= Overview of Georgia Tech Algorithms =

At Georgia Tech, we are broadly interested in a range of mathematical image analysis algorithms for segmentation, registration, diffusion-weighted MRI analysis, and statistical analysis. For many applications, we cast the problem in an energy minimization framework wherein we define a partial differential equation whose numeric solution corresponds to the desired algorithmic outcome. The following are many examples of PDE techniques applied to medical image analysis.

= Georgia Tech Projects =

{| cellpadding="10"
| style="width:15%" | [[Image:Gatech caudateBands.PNG|200px]]
| style="width:85%" |

== [[Projects:MultiscaleShapeSegmentation|Multiscale Shape Segmentation Techniques]] ==

To represent multiscale variations in a shape population in order to drive the segmentation of deep brain structures, such as the caudate nucleus or the hippocampus. [[Projects:MultiscaleShapeSegmentation|More...]]

'''New: ''' Delphine Nain won the best student paper at [[MICCAI_2006|MICCAI 2006]] in the category "Segmentation and Registration" for her paper entitled "Shape-driven surface segmentation using spherical wavelets" by D. Nain, S. Haker, A. Bobick, A. Tannenbaum.

|-

| | [[Image:ZoomedResultWithModel.png|200px]]
| |

== [[Projects:GeodesicTractographySegmentation|Geodesic Tractography Segmentation]] ==

In this work, we provide an energy minimization framework which allows one to find fiber tracts and volumetric fiber bundles in brain diffusion-weighted MRI (DW-MRI). [[Projects:GeodesicTractographySegmentation|More...]]

'''New: ''' J. Melonakos, E. Pichon, S. Angenet, and A. Tannenbaum. Finsler Active Contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, March 2008, Vol 30, Num 3.

|-

| | [[Image:Results brain sag.JPG|200px|]]
| |

== [[Projects:OptimalMassTransportRegistration|Optimal Mass Transport Registration]] ==

The goal of this project is to implement a computationaly efficient Elastic/Non-rigid Registration algorithm based on the Monge-Kantorovich theory of optimal mass transport for 3D Medical Imagery. Our technique is based on Multigrid and Multiresolution techniques. This method is particularly useful because it is parameter free and utilizes all of the grayscale data in the image pairs in a symmetric fashion and no landmarks need to be specified for correspondence. [[Projects:OptimalMassTransportRegistration|More...]]

'''New: ''' Tauseef ur Rehman, A. Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. SPIE Conference on Computational Imaging V, Jan 2007.

|-

| | [[Image:Caudate Nucleus Denoising.JPG|200px|]]
| |

== [[Projects:WaveletShrinkage|Wavelet Shrinkage for Shape Analysis]] ==

Shape analysis has become a topic of interest in medical imaging since local variations of a shape could carry relevant information about a disease that may affect only a portion of an organ. We developed a novel wavelet-based denoising and compression statistical model for 3D shapes. [[Projects:WaveletShrinkage|More...]]

'''New: ''' Bayesian Spherical Wavelet Shrinkage:Applications to shape analysis, X. Le Faucheur, B. Vidakovic, A. Tannenbaum, Proc. of SPIE Optics East, 2007.

|-

| | [[Image:TruckInitialization.png|200px|]]
| |

== [[Projects:PointSetRigidRegistration|Point Set Rigid Registration]] ==

In this work, we propose a particle filtering approach for the problem of registering two point sets that differ by
a rigid body transformation. Experimental results are provided that demonstrate the robustness of the algorithm to initialization, noise, missing structures or differing point densities in each sets, on challenging 2D and 3D registration tasks. [[Projects:PointSetRigidRegistration|More...]]

'''New: ''' R. Sandhu, S. Dambreville, A. Tannenbaum. Particle Filtering for Registration of 2D and 3D Point Sets with Stochastic Dynamics. In CVPR, 2008.

|-

| | [[Image:Dlpfc1.jpg|200px|]]
| |

== [[Projects:RuleBasedDLPFCSegmentation|Rule-Based DLPFC Segmentation]] ==

In this work, we provide software to semi-automate the implementation of segmentation procedures based on expert neuroanatomist rules for the dorsolateral prefrontal cortex. [[Projects:RuleBasedDLPFCSegmentation|More...]]

'''New: ''' Al-Hakim, et al. A Dorsolateral Prefrontal Cortex Semi-Automatic Segmenter. SPIE MI 2006.

|-

| | [[Image:Striatum1.png|200px|]]
| |

== [[Projects:RuleBasedStriatumSegmentation|Rule-Based Striatum Segmentation]] ==

In this work, we provide software to semi-automate the implementation of segmentation procedures based on expert neuroanatomist rules for the striatum. [[Projects:RuleBasedStriatumSegmentation|More...]]

'''New: ''' Al-Hakim, et al. Parcellation of the Striatum. SPIE MI 2007.

|-

| | [[Image:Brain-flat.PNG|200px]]
| |

== [[Projects:ConformalFlatteningRegistration|Conformal Flattening]] ==

The goal of this project is for better visualizing and computation of neural activity from fMRI brain imagery. Also, with this technique, shapes can be mapped to shperes for shape analysis, registration or other purposes. Our technique is based on conformal mappings which map genus-zero surface: in fmri case cortical or other surfaces, onto a sphere in an angle preserving manner. [[Projects:ConformalFlatteningRegistration|More...]]

'''New: ''' Y. Gao, J. Melonakos, and A. Tannenbaum. Conformal Flattening ITK Filter. ISC/NA-MIC Workshop on Open Science at MICCAI 2006.

|-

| | [[Image:Basis membership.png|200px]]
| |

== [[Projects:MultiscaleShapeAnalysis|Multiscale Shape Analysis]] ==

We present a novel method of statistical surface-based morphometry based on the use of non-parametric permutation tests and a spherical wavelet (SWC) shape representation. [[Projects:MultiscaleShapeAnalysis|More...]]

'''New: ''' D. Nain, M. Styner, M. Niethammer, J. J. Levitt, M E Shenton, G Gerig, A. Bobick, A. Tannenbaum. Statistical Shape Analysis of Brain Structures using Spherical Wavelets. Accepted in The Fourth IEEE International Symposium on Biomedical Imaging (ISBI ’07) that will be held April 12-15, 2007 in Metro Washington DC, USA.

|-

| | [[Image:Circle seg.PNG|200px|]]
| |

== [[Projects:KPCASegmentation|Kernel PCA for Segmentation]] ==

Segmentation performances using active contours can be drastically improved if the possible shapes of the object of interest are learnt. The goal of this work is to use Kernel PCA to learn shape priors. Kernel PCA allows for learning non linear dependencies in data sets, leading to more robust shape priors. [[Projects:KPCASegmentation|More...]]

'''New: ''' S. Dambreville, Y. Rathi, and A. Tannenbaum. A Framework for Image Segmentation using Image Shape Models and Kernel PCA Shape Priors. PAMI. Submitted to PAMI.

|-

| | [[Image:Fig1yan.PNG|200px|]]
| |

== [[Projects:BloodVesselSegmentation|Blood Vessel Segmentation]] ==

The goal of this work is to develop blood vessel segmentation techniques for 3D MRI and CT data. The methods have been applied to coronary arteries and portal veins, with promising results. [[Projects:BloodVesselSegmentation|More...]]

'''New: '''Y. Yang, S. George, D. Martin, A. Tannenbaum, and D. Giddens. 3D Modeling of Patient-Specific Geometries of Portal Veins Using MR Images. In Proceedings IEEE EMBS, 2006

|-

| | [[Image:Fig67.png|200px|]]
| |

== [[Projects:KnowledgeBasedBayesianSegmentation|Knowledge-Based Bayesian Segmentation]] ==

This ITK filter is a segmentation algorithm that utilizes Bayes's Rule along with an affine-invariant anisotropic smoothing filter. [[Projects:KnowledgeBasedBayesianSegmentation|More...]]

'''New: ''' J. Melonakos, Y. Gao, and A. Tannenbaum. Tissue Tracking: Applications for Brain MRI Classification. SPIE Medical Imaging, 2007.

|-

| | [[Image:Stochastic-snake.png|200px|]]
| |

== [[Projects:StochasticMethodsSegmentation|Stochastic Methods for Segmentation]] ==

New stochastic methods for implementing curvature driven flows for various medical tasks such as segmentation. [[Projects:StochasticMethodsSegmentation|More...]]

'''New: ''' Currently under investigation.

|-

| | [[Image:Table1.png|200px|]]
| |

== [[Projects:KPCA_LLE_KLLE_ShapeAnalysis|KPCA, LLE, KLLE Shape Analysis]] ==

The goal of this work is to study and compare shape learning techniques. The techniques considered are Linear Principal Components Analysis (PCA), Kernel PCA, Locally Linear Embedding (LLE) and Kernel LLE. [[Projects:KPCA_LLE_KLLE_ShapeAnalysis|More...]]

'''New: ''' Y. Rathi, S. Dambreville, and A. Tannenbaum. "Comparative Analysis of Kernel Methods for Statistical Shape Learning", In CVAMIA held in conjunction with ECCV, 2006.

|-

| | [[Image:Gatech SlicerModel2.jpg|200px]]
| |

== [[Projects:StatisticalSegmentationSlicer2|Statistical/PDE Methods using Fast Marching for Segmentation]] ==

This Fast Marching based flow was added to Slicer 2. [[Projects:StatisticalSegmentationSlicer2|More...]]

|-

| | [[Image:P1_small.png|200px|]]
| |

== [[Projects:LabelSpace|Label Space: A Coupled Multi-Shape Representation]] ==

Many techniques for multi-shape representation may often develop inaccuracies stemming from either approximations or inherent variation. Label space is an implicit representation that offers unbiased algebraic manipulation and natural expression of label uncertainty. We demonstrate smoothing and registration on multi-label brain MRI. [[Projects:LabelSpace|More...]]

J. Malcolm, Y. Rathi, A. Tannenbaum. "Label Space\: A Multi-Object Shape Representation." In Combinatorial Image Analysis, 2008.

|-

| | [[Image:Prostate20080318 seg.png|200px|]]
| |

== [[Projects:ProstateSegmentatio|Prostate segmentation]] ==

The 3D ultrasound images are collected by collaborators at Queen’s University. With a little manual initialization, the algorithm provided the results give to the left. The method incorporates Cellular Automata and Geodesic Active Contour. [[Projects:ProstateSegmentatio|More...]]

File:Caudate Nucleus Denoising.JPG

2008-04-28T19:09:47Z

Xavier: