| note
| - In the field of bioinformatics, clustering recently appeared to be a very efficient technique for sequence analysis. While greedy and hierarchical algorithms are used in the majority of the available tools, spectral clustering was recently introduced as a new stakeholder in this field. Spectral clustering is an efficient technique for well-separated sequence clustering and GMM's (Gaussian Mixture Models) are often able to cluster overlapping groups given an adequately designed embedding. Yet, the available clustering tools, for biological sequences, present many drawbacks especially that i- the most widely used ones require an accurate choice of a non-obvious identity or similarity threshold, ii- most of them are not designed to cluster potentially divergent sequences, and iii- the recent one that relies on the spectral clustering technique, and that does not require any user intervention or prior knowledge about the input sequences, is so slow and was not enough tested and validated. Moreover, the performance of several well-known clustering techniques is not assessed in the field of clustering biological sequences.Firstly, since the recent clustering technique that relies on spectral clustering offered a potential solution for the drawbacks of the traditional tools, its own drawbacks are being addressed and an enhancement in its computation time is achieved. This enhancement is based on improving the required time for the pairwise affinity computation of the sequences. The proposed solution is to adopt a parallel computation scheme for the pairwise affinity computation. This solution has been implemented according to the master/slave distributed architecture, using Message Passing Interface (MPI), and showed a drastic improvement in the computation time. Moreover, the resulting clustering package, named SpCLUST, was intensively evaluated on simulated and real genomic and protein data sets. The clustering results were compared to the most known traditional tools, such as UCLUST, CD-HIT, and DNACLUST. The comparison showed that SpCLUST outperforms the other tools when clustering divergent sequences.Secondly, further improvements to SpCLUST, speed-wise, accuracy-wise, and feature-wise, were introduced. The implemented approach in SpCLUST results in a pipeline of the following steps: i- sequence alignment, ii- pairwise affinity computation of the sequences, iii- Laplacian Eigenmap embedding of the data, and iv- GMM based clustering. Therefore, improving the quality of the generated clustering and the performance of this approach is directly related to the enhancement of each of these five steps: the alignment quality, the appropriate design of the affinity, the GMM implementation, etc. Accordingly, we have written a completely new C++ GMM library incorporating new features and options for optimizing the clustering speed and quality. This resulted in a second release, namely SpCLUST-V2, of our package. Moreover, the impact of using different modules, methods, implementations, and algorithms (sequence alignment modules, various clustering methods, GMM implementations, and affinity matrix types) in this process pipeline is carefully discussed.Finally, a major improvement in the speed of the pairwise affinity computation is achieved by adopting a new library in our package. Moreover, a novel clustering technique is introduced. Furthermore, additional clustering techniques were explored on biological sequences, and a qualitative study compares their performance and accuracy. The used implementations were embedded in SpCLUST-Global, an improved cross-platform biological sequences' clustering package. SpCLUST-Global outperforms its GMM-based predecessors in terms of speed and handling data sets that contain large genomes. It also outperforms the state-of-the-art tools in clustering hybrid and highly divergent data sets. The versions of our package are freely available online.
- Dans le domaine de la bioinformatique, le clustering est une technique efficace pour l'analyse des séquences. Le clustering spectral a récemment été introduit comme un nouvel acteur dans ce domaine. C’est une technique efficace pour le clustering de séquences bien séparées et les GMM sont souvent capables de partitionner des groupes qui intersectent. Pourtant, les outils de clustering disponibles, pour les séquences biologiques, présentent de nombreux obstacles: i- les plus utilisés nécessitent un choix précis d'un seuil d'identité ou de similarité qui n'est pas toujours évident, ii- la plupart d'entre eux ne sont pas conçus pour regrouper des séquences assez divergentes, et iii- une technique récente, qui repose sur le clustering spectral, et qui ne nécessite aucune connaissance préalable des propriétés des séquences d'entrée, est assez lente et n'a pas été suffisamment validée. De plus, les performances de plusieurs techniques de clustering bien connues ne sont toujours pas évaluées dans le domaine du clustering de séquences biologiques.Tout d'abord, étant donné que la technique récente qui repose sur le clustering spectral offre une solution aux obstacles connus des outils traditionnels, des solutions à ses propres obstacles seront visée. Cette amélioration est basée sur la réduction du temps requis pour le calcul d'affinité par paires de séquences. La solution proposée est d'adopter un schéma de calcul parallèle pour ce calcul. Cette solution a été implémentée, selon l'architecture distribuée maître/esclave, en utilisant la MPI, et a montré une amélioration considérable du temps de calcul. De plus, l'outil de clustering résultant, nommé SpCLUST, a été intensivement évalué sur des ensembles de données génomiques et protéiques. Les résultats du clustering ont été comparés à celui des outils traditionnels les plus connus, tels que UCLUST, CD-HIT et DNACLUST. La comparaison a montré que SpCLUST surpasse les autres outils lors du regroupement de séquences divergentes.Ensuite, d'autres améliorations de SpCLUST, en termes de vitesse, de précision et de fonctionnalités, ont été introduites. L'approche implémentée dans SpCLUST consiste des étapes suivantes : i- alignement de séquences, ii- calcul d'affinité par paires de séquences, iii- intégration des données sur la Eigenmap laplacienne et iv- clustering basé sur GMM. Par conséquent, l'amélioration de la qualité du clustering généré et des performances de cette approche est directement liée à l'amélioration de la qualité de l'alignement, la conception appropriée de l'affinité, l'implémentation GMM, etc. En conséquence, nous avons écrit une bibliothèque GMM intégrant de nouvelles fonctionnalités et options pour optimiser la vitesse et la qualité du clustering. Cela a abouti à une deuxième version de notre outil, nommée SpCLUST-V2. De plus, l'impact de l'utilisation de différents modules, méthodes, implémentations et algorithmes dans ce pipeline de processus est soigneusement discuté.Enfin, une accéleration majeure de la vitesse du calcul d'affinité par paire est obtenue en adoptant une nouvelle bibliothèque dans notre package. De plus, une nouvelle technique de clustering est introduite. Aussi, des techniques de clustering supplémentaires ont été explorées sur des séquences biologiques, et une étude qualitative est présentée pour leurs résultats. Ces résultats sont également comparés à ceux de certains outils traditionnels. Les implémentations utilisées ont été intégrées dans SpCLUST-Global, un outil amélioré de regroupement de séquences biologiques multiplateformes. SpCLUST-Global surpasse ses prédécesseurs qui sont basés sur GMM, en termes de vitesse et de gestion des ensembles de données contenant de grands génomes. Il surpasse également les outils traditionnels en termes de justesse de regroupement d'ensembles de données hybrides et très divergents. Les différentes versions de notre outil sont disponibles gratuitement en ligne.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
