McAN: an ultrafast haplotype network construction algorithm

Abstract

SummaryHaplotype network is becoming popular due to its increasing use in analyzing genealogical relationships of closely related genomes. We newly proposed McAN, a minimum-cost arborescence based haplotype network construction algorithm, by considering mutation spectrum history (mutations in ancestry haplotype should be contained in descendant haplotype), node size (corresponding to sample count for a given node) and sampling time. McAN is two orders of magnitude faster than the state-of-the-art algorithms, making it suitable for analyzation of massive sequences. AvailabilitySource code is written in C/C++ and available at https://github.com/Theory-Lun/McAN and https://ngdc.cncb.ac.cn/biocode/tools/BT007301 under the MIT license. The online web service of McAN is available at https://ngdc.cncb.ac.cn/ncov/online/tool/haplotype. SARS-CoV-2 dataset are available at https://ngdc.cncb.ac.cn/ncov/.