The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3549851 | PMC |
| http://dx.doi.org/10.1186/1471-2105-14-S2-S18 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Stacked-ring aromaticity from the viewpoint of the effective number of π-electrons.
Chem Sci
December 2024
Department of Materials Engineering Science, Graduate School of Engineering Science, Osaka University Toyonaka Osaka 560-8531 Japan
In this study, we theoretically examined the mechanism of aromaticity induced in closely stacked cofacial π-dimers of 4π antiaromatic molecules, which is called stacked-ring aromaticity, in terms of the effective number of π-electrons ( ) and Baird's rule. High-precision quantum chemical calculations combined with a multi-configurational wavefunction analysis revealed that double-triplet [(TT)] and intermolecular charge-transfer (CT) electron configurations mix substantially in the ground state wavefunctions of cyclobutadiene and Ni(ii) norcorrole dimer models at small stacking distance (). Since the T configuration gives rise to two unpaired electrons, the remaining 4 - 2 π electrons still participate in the intramolecular conjugation, which can be interpreted as the origin of the aromaticity of each monomer.
View Article and Find Full Text PDFThermodynamic Stability in Transition Metal-Hydrogen Dications: Potential Energy Curves, Spectroscopic Parameters, and Bonding for VH.
J Comput Chem
January 2025
Universidade de São Paulo, Instituto de Química, Departamento de Química Fundamental, São Paulo, Brazil.
Seventeen electronic states of the dication VH were characterized by the SA-CASSCF/icMRCI methodology using very extended basis sets; 11 were described for the first time. Potential energy curves were constructed and the associated spectroscopic parameters evaluated. Triplet and quintet states correlating with the V + H channel are thermodynamic stable.
View Article and Find Full Text PDFMask-guided network for finger vein feature extraction and biometric identification.
Biomed Opt Express
December 2024
Yangtze Delta Region Institute (Huzhou), University of Electronic Science and Technology of China (UESTC), Huzhou 313001, China.
The problems of complex background, low quality of finger vein images, and poor discriminative features have been the bottleneck of feature extraction and finger vein recognition. To this end, we propose a feature extraction algorithm based on the open-set testing protocol. In order to eliminate the interference of irrelevant areas, this paper proposes the idea of segmentation-assisted classification, that is, using the rough mask of the finger vein to constrain the feature learning process so that the network can focus on the vein area and learn greater weight for the vein.
View Article and Find Full Text PDFTriplet Network for One-Shot Raman Spectrum Recognition.
Appl Spectrosc
December 2024
Key Laboratory of Drugs Analysis & Intelligent-Monitoring, Narcotics Technology Center of Shaanxi Provincial Public Security Department, National Narcotics Laboratory Shaanxi Regional Center, Shaanxi, China.
Raman spectroscopy is widely used for material detection due to its specificity, but its application to spectral recognition often faces limitations due to insufficient training data, unlike fields such as image recognition. Traditional machine learning or basic neural networks are commonly used, but they have limited ability to achieve high precision. We have proposed a novel approach that combines the Triplet network (TN) and K-nearest neighbor (KNN) techniques to address this issue.
View Article and Find Full Text PDFSemantic Mask Reconstruction and Category Semantic Learning for few-shot image generation.
Neural Netw
December 2024
Key Laboratory of Smart Manufacturing in Energy Chemical Process, East China University of Science and Technology, Shanghai, 200237, China; Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, 200237, China. Electronic address:
Few-shot image generation aims at generating novel images for the unseen category when given K images from the same category. Despite significant advancements in existing few-shot image generation methods, great challenges remain regarding the quality and diversity of the generated images. This issue stems from the model's struggle to fully comprehend the semantic content of images and extract sufficiently semantic representations.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!