基于广义超曲面树的相似性搜索算法

相似性搜索是数据挖掘的主要领域之一.它在数据库中检索出相似的数据,发现数据间的相似性.它可以应用于图像数据库、空间数据库和时间序列分析.对于欧氏空间(一种特殊的度量空间),相似性搜索算法中基于R-tree的方法,在低维时是高效的,当维数增加时,R-tree的方法将退化为线性扫描.该现象被称为维数灾难(dimensionality curse),主要原因是存在数据重复.当数据量很大且维数很高时,距离计算和I/O操作将非常费时.提出了度量空间上新的空间分割方法和索引结构rgh-tree,利用数据库的数据对象与很少几个固定参考对象的距离信息进行数据分割和分布,产生一个各节点没有数据重复的平衡树.另外,在rgh-tree的基础上提出了相应的相似性搜索算法,该算法具有较小的I/O代价和距离计算次数,平均复杂性近似为o(n0.58).解决了目前算法存在的一些问题.

中国蜘蛛抱蛋属植物DNA条形码研究

利用植物DNA条形码候选序列mat K、psb A-trn H、psb K-psb I和rbc L对蜘蛛抱蛋属(Aspidistra)植物的19种104批样品进行扩增和测序,并采用相似性搜索算法(BLAST)对各序列的鉴定效率进行评价,得出蜘蛛抱蛋属物种鉴定的最佳序列。结果显示,psb K-psb I的物种鉴定成功率为88.7%,在单一序列中成功率最高。通过多序列组合鉴定效率的比较,发现组合序列的鉴定成功率明显高于单一序列,其中mat K+(psb K-psb I)组合的鉴定成功率高达100%,基于该序列组合构建蜘蛛抱蛋属植物的系统发育树,结果显示同一物种的样品聚集度较好,多表现为单系。研究结果表明mat K+(psb K-psb I)序列组合可作为蜘蛛抱蛋植物种鉴定的最佳条形码序列。