A computationally efficient approximation to the nearest neighbor interchange metric

The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in terms of a simple transformation of binary trees, but its use in nontrivial problems is usually prevented by the absence of a computationally efficient algorithm. Since recent attempts to discover such an algorithm continue to be unsuccessful, we address the complementary problem of designing an approximation to the nni metric. Such an approximation should be well-defined, efficient to compute, comprehensible to users, relevant to applications, and a close fit to the nni metric; the challenge, of course, is to compromise these objectives in such a way that the final design is acceptable to users with practical and theoretical orientations. We describe an approximation algorithm that appears to satisfy adequately these objectives. The algorithm requires O(n) space to compute dissimilarity between binary trees withn labeled leaves; it requires O(n logn) time for rooted trees and O(n ² logn) time for unrooted trees. To help the user interpret the dissimilarity measures based on this algorithm, we describe empirical distributions of dissimilarities between pairs of randomly selected trees for both rooted and unrooted cases.The Natural Sciences and Engineering Research Council of Canada partially supported this work with Grant A-4142.     

20世纪一次成功的中瑞合作科学考察——西北科学考查团

上个世纪中瑞合作的西北科学考查团是一个富有成效的科考团体。从合作一开始就展现了双方较高的智慧，他们围绕西北考察这一共同目标达成共识。最终瑞方达到为“开辟航线”收集气象、地理、地磁等各种资料的目的，中方达到维护主权，考察西部边陲和培养人才的目的。在中国科技史和中外科技交流史上书写了非常有意义的一页。