De Novo Alcorithm For Glycan Interpretation From MS/MS

Polysaccharide is composed of multiple monosaccharide molecules condensation, They are kinds of molecular mechanism that are complex and huge, not only very widely distributed in nature, but also play an important role in life activities Polysaccharide are components of animal and plant cell wall, peptidoglycan and cellulose; They can also be found in the form of glycogen or starch as the energy storage substances in plants and animals; And polysaccharide in specific biological activity play important roles in catalytic. Many diseases such as clotting abnormalities, immune system imbalance and some neurological diseases are also associated with specific polysaccharides. In recent years, many researchers on polysaccharides have done a lot of analysis and research work in the area. Computer-aided as an important tool in determining polysaccharide structure can effectively solve the high cost of pure biochemistry method, low efficiency, and it can help to get more accurate results. Mass spectrometer is indispensable to bioinformatics in instruments, it use different biological macro-molecular mass-to-charge ratio (mass-charge ratio).Currently, the main polysaccharide structure parsing algorithm is divided into two categories, category in the process of parsing directly using the polysaccharide in the database information; Another kind of polysaccharide in the process of resolution without reference to database. Although in recent years, De novo parsing polysaccharide structure (including the monosaccharide composition, arrangement of information and connection information between monosaccharide) have been paid much attention by researchers, there have been many breakthrough algorithms, but so far the algorithms on the accuracy and speed still leave great room for improvement. De novo algorithm can be further classified as the accurate analytical algorithms and accurate analytical algorithm. Inaccurate analytical algorithms often use heuristic method to select the correct structure of roughly range, although fast, but the number of their candidate structures are generally bigger, lose the practical significance of the analytical structure. While the latter usually use the pruning method or dynamic programming algorithm, these algorithms’time complexity is higher. In order to speed up the algorithms, many assumptions and idealized model are used,some limited the scope of these analytical polysaccharide to reduce the difficulty of the problem. So far, De novoalgorithm prediction result has much room to improve. In addition, the existing method of De novo in the reconstruction of polysaccharide structure often adopt tree structure glycan model, although simple and intuitive, but not so convenient for binary polysaccharide and trigeminal polysaccharide, as these algorithms have to offer different iterative formulas for each; Tree representation model also has difficulty in describing details such as the connection between monosaccharide of polysaccharides. The paper tries to put forward a method based on graph, the method is adopted to improve the polysaccharide interpretation efficiency. Under this model, a unified iterative formula is given. The inputs of the algorithm are the mass spectrometer, the paper proposes the mass spectrum. Due to the biological experimental environment, and the instrument can produce interference of spectra, and the influence of the purity of polysaccharide compounds.The paper proposes a noise reduction processing for mass spectrum data preprocessing step, at the same time, in order to make the results more practical, it is necessary to reduce the number of candidates for structure, therefore, this article also gives the structure of a candidate screening of post-processing step. We integrate them in a complete parsing algorithm procedure. In the specific process of iteration, we adopted different iterative method with the existing work, the algorithm of the growth of the unit is no longer a simple sugars, but the substructure in the algorithm, which makes the running time of the algorithm shorter.