计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2013年
11期
27-33
,共7页
单体分型%聚类%大规模计算%并行计算%生物信息学
單體分型%聚類%大規模計算%併行計算%生物信息學
단체분형%취류%대규모계산%병행계산%생물신식학
haplotype phasing%clustering%large-scale computing%parallel computing%bioinformatics
大规模单体分型问题是生物遗传分析领域一个重要的基础性问题.针对现有算法求解大规模单体分型问题时存在的缺陷,在原有WinHAP算法的基础上引入聚类思想,提出一种基于聚类的Win-HAP算法.该算法在保证原算法精度不下降的前提下,大大提高了算法的计算速度,降低了空间消耗,并具有空间需求与序列条数无关这一优良特性,因此特别适合处理超大规模的数据集.在SIMD共享存储模型下对算法进行了并行化,并设计了基于贪心的线程任务分配策略,获得了接近线性的加速比.
大規模單體分型問題是生物遺傳分析領域一箇重要的基礎性問題.針對現有算法求解大規模單體分型問題時存在的缺陷,在原有WinHAP算法的基礎上引入聚類思想,提齣一種基于聚類的Win-HAP算法.該算法在保證原算法精度不下降的前提下,大大提高瞭算法的計算速度,降低瞭空間消耗,併具有空間需求與序列條數無關這一優良特性,因此特彆適閤處理超大規模的數據集.在SIMD共享存儲模型下對算法進行瞭併行化,併設計瞭基于貪心的線程任務分配策略,穫得瞭接近線性的加速比.
대규모단체분형문제시생물유전분석영역일개중요적기출성문제.침대현유산법구해대규모단체분형문제시존재적결함,재원유WinHAP산법적기출상인입취류사상,제출일충기우취류적Win-HAP산법.해산법재보증원산법정도불하강적전제하,대대제고료산법적계산속도,강저료공간소모,병구유공간수구여서렬조수무관저일우량특성,인차특별괄합처리초대규모적수거집.재SIMD공향존저모형하대산법진행료병행화,병설계료기우탐심적선정임무분배책략,획득료접근선성적가속비.
